問題描述 小明的實驗室有N臺電腦，編號1~N。原本這N臺電腦之間有N-1條數據鏈接相連，恰好構成一個樹形網絡。在樹形網絡上，任意兩臺電腦之間有唯一的路徑相連。


　　不過在最近一次維護網絡時，管理員誤操作使得某兩臺電腦之間增加了一條數據鏈接，于是網絡中出現了環路。環路上的電腦由于兩兩之間不再是只有一條路徑，使得這些電腦上的數據傳輸出現了BUG。


　　為了恢復正常傳輸。小明需要找到所有在環路上的電腦，你能幫助他嗎？ 輸入格式 第一行包含一個整數N。
　　以下N行每行兩個整數a和b，表示a和b之間有一條數據鏈接相連。


　　對于30%的數據，1 <= N <= 1000
　　對于100%的數據, 1 <= N <= 100000， 1 <= a, b <= N


　　輸入保證合法。 輸出格式 按從小到大的順序輸出在環路上的電腦的編號，中間由一個空格分隔。 樣例輸入 5
1 2
3 1
2 4
2 5
5 3 樣例輸出

1 2 3 5

分析：?可以利用一個棧?任意取一個點開始搜索?然后把所有沒入棧的元素入棧?只要沒有重復元素入棧?就一直搜索下去?由于本來就是一棵樹?并且只有一個環?所以當我們遇到重復入棧的元素的時候?就不斷彈出?知道把問題元素彈完為止?那么就相當于把這個環中的所有元素都彈出來了

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+10; stack<int>S; priority_queue<int,vector<int>,greater<int> >pq; vector<int>g[maxn]; bool fin,bok[maxn]; void dfs(int x,int f){if(!bok[x]){bok[x] = 1;S.push(x);for(int i=0;i<g[x].size();i++){int t = g[x][i];if(t!=f)dfs(t,x);if(fin)return; }if(S.top()==x){S.pop();}}else{while(1){int t ;if(!S.empty()){t = S.top();S.pop();pq.push(t);bok[t] = false;if(t==x)break;}}if(pq.size()>1){fin=1;return;}} } int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){int s,e;scanf("%d%d",&s,&e);g[s].push_back(e);g[e].push_back(s);}dfs(1,-1);while(!pq.empty()){int t = pq.top();pq.pop();if(pq.size()==0)printf("%d\n",t);else printf("%d ",t);} return 0; }

拓撲排序也可以做

#include<bits/stdc++.h> #include<set> using namespace std; set<int>g[1000010]; bool del[1000010]; int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){int s,e;scanf("%d%d",&s,&e);g[s].insert(e);g[e].insert(s); } int cnt=0;queue<int>que;for(int i=1;i<=n;i++){if(g[i].size()==1)que.push(i); }while(!que.empty()){int t = que.front();que.pop();for(set<int>::iterator i=g[t].begin();i!=g[t].end();i++){int now = *i;g[now].erase(t);if(g[now].size()==1){que.push(now);cnt++;}}g[t].clear(); }for(int i=1;i<=n;i++){if(g[i].size()){cnt--;if(cnt==0)printf("%d\n",i);else printf("%d ",i);} }return 0; }

總結

以上是生活随笔為你收集整理的2017蓝桥杯决赛-发现环 数据结构|搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。