小明的實(shí)驗(yàn)室有N臺(tái)電腦，編號(hào)1~N。原本這N臺(tái)電腦之間有N-1條數(shù)據(jù)鏈接相連，恰好構(gòu)成一個(gè)樹形網(wǎng)絡(luò)。在樹形網(wǎng)絡(luò)上，任意兩臺(tái)電腦之間有唯一的路徑相連。
不過在最近一次維護(hù)網(wǎng)絡(luò)時(shí)，管理員誤操作使得某兩臺(tái)電腦之間增加了一條數(shù)據(jù)鏈接，于是網(wǎng)絡(luò)中出現(xiàn)了環(huán)路。環(huán)路上的電腦由于兩兩之間不再是只有一條路徑，使得這些電腦上的數(shù)據(jù)傳輸出現(xiàn)了BUG。
為了恢復(fù)正常傳輸。小明需要找到所有在環(huán)路上的電腦，你能幫助他嗎？
輸入
第一行包含一個(gè)整數(shù)N。
以下N行每行兩個(gè)整數(shù)a和b，表示a和b之間有一條數(shù)據(jù)鏈接相連。
對(duì)于30%的數(shù)據(jù)，1 <= N <= 1000
對(duì)于100%的數(shù)據(jù), 1 <= N <= 100000， 1 <= a, b <= N
輸入保證合法。
輸出
按從小到大的順序輸出在環(huán)路上的電腦的編號(hào)，中間由一個(gè)空格分隔。
樣例輸入
5
1 2
3 1
2 4
2 5
5 3
樣例輸出
1 2 3 5
思路：很水的一個(gè)題目了。直接判斷環(huán)上面的節(jié)點(diǎn)，拓?fù)渑判颉?br /> 代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; int deg[maxx]; vector<int> p[maxx]; int n;int main() {scanf("%d",&n);int x,y;memset(deg,0,sizeof(deg));for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);deg[x]++,deg[y]++;p[x].push_back(y);p[y].push_back(x);}queue<int> q;for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i);while(q.size()){int u=q.front();q.pop();deg[u]=-1;for(int i=0;i<p[u].size();i++){deg[p[u][i]]--;if(deg[p[u][i]]==1) q.push(p[u][i]);}}for(int i=1;i<=n;i++) if(deg[i]>0) cout<<i<<" ";cout<<endl; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯之小明判断环的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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