題目鏈接
題目描述
小明的實驗室有N臺電腦，編號1~N。原本這N臺電腦之間有N-1條數(shù)據(jù)鏈接相連，恰好構(gòu)成一個樹形網(wǎng)絡(luò)。在樹形網(wǎng)絡(luò)上，任意兩臺電腦之間有唯一的路徑相連。
不過在最近一次維護(hù)網(wǎng)絡(luò)時，管理員誤操作使得某兩臺電腦之間增加了一條數(shù)據(jù)鏈接，于是網(wǎng)絡(luò)中出現(xiàn)了環(huán)路。環(huán)路上的電腦由于兩兩之間不再是只有一條路徑，使得這些電腦上的數(shù)據(jù)傳輸出現(xiàn)了BUG。
為了恢復(fù)正常傳輸。小明需要找到所有在環(huán)路上的電腦，你能幫助他嗎？

題解：

問題是求出圖中的環(huán)，并順序輸出環(huán)中元素
有兩個方法可以做：
第一個是用拓?fù)渑判蚍?#xff0c;點度數(shù)為1的肯定不在環(huán)內(nèi)，如果與度為1的點相連的邊-1后度也是1的話肯定也不是
最后沒有被標(biāo)記的點就是答案
還一個方法是用并查集+dfs
用并查集對不同塊的點進(jìn)行連接，如果發(fā)現(xiàn)兩個點已經(jīng)在一個塊內(nèi)，說明這兩個點在環(huán)上，那么就拿一個點作為起點一個點作為終點，dfs遍歷順序輸出即可

代碼：

#include<bits/stdc++.h> #define x first #define y second #define mem(h) memset(h,-1,sizeof h) #define mcp(a,b) memcpy(a,b,sizeof b) using namespace std; typedef long long LL; typedef unsigned long long ull; typedef pair<int,int>PII; typedef pair<double,double>PDD; namespace IO{inline LL read(){LL o=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}return o*f;} }using namespace IO; //#############以上是自定義技巧（可忽略）########## const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131; int h[N],e[M],ne[M],idx; int d[N]; bool st[N]; int n; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void topo(){queue<int>q;for(int i=1;i<=n;i++){if(d[i]==1){//把所有度為1的點放去隊列q.push(i);st[i]=1;}}while(!q.empty()){int u=q.front();q.pop();for(int i=h[u];~i;i=ne[i]){int j=e[i];if(st[j])continue;if(--d[j]==1){//如果與度為1的點相連的邊-1后度也是1的話，那么加入隊列q.push(j);st[j]=1;}}} } int main(){mem(h);cin>>n;for(int a,b,i=0;i<n;i++){cin>>a>>b;add(a,b),add(b,a);//建邊d[a]++,d[b]++;//度+1}topo();//拓?fù)渑判?/span>for(int i=1;i<=n;i++){if(!st[i])cout<<i<<" ";}return 0; } #include<bits/stdc++.h> #define x first #define y second #define mem(h) memset(h,-1,sizeof h) #define mcp(a,b) memcpy(a,b,sizeof b) using namespace std; typedef long long LL; typedef unsigned long long ull; typedef pair<int,int>PII; typedef pair<double,double>PDD; namespace IO{inline LL read(){LL o=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}return o*f;} }using namespace IO; //#############以上是自定義技巧（可忽略）########## const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131; int h[N],e[M],ne[M],idx; int ans[N]; bool st[N]; int fa[N]; int n; int sx,ex; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]); } void dfs(int x,int cnt){//x表示當(dāng)前點，cnt表示當(dāng)前答案下標(biāo)ans[cnt]=x;//當(dāng)前答案下標(biāo)放x點if(x==ex){//如果已經(jīng)到達(dá)最終點sort(ans,ans+cnt+1);//就把答案排序for(int i=0;i<=cnt;i++){cout<<ans[i]<<" ";}cout<<endl;return ;}st[x]=1;//標(biāo)記已經(jīng)來過for(int i=h[x];~i;i=ne[i]){//搜索相鄰的的點int j=e[i];if(st[j])continue;dfs(j,cnt+1);}st[x]=0; } int main(){mem(h);cin>>n;for(int i=0;i<=n;i++)fa[i]=i;int a,b;for(int i=0;i<n;i++){cin>>a>>b;if(find(a)!=find(b)){//如果不在一個集合就合并，并建邊fa[find(a)]=find(b);add(a,b),add(b,a);}else{sx=a,ex=b;//如果在一個集合就證明兩個點在環(huán)里，一個作為起始點，一個作為最終點}}dfs(sx,0);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][2017年第八届真题]发现环的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。