試題 歷屆試題 發現環

---

資源限制
時間限制：1.0s 內存限制：256.0MB

$Daily English

雖然世界充滿苦難，但是苦難總是可以戰勝的。
While the world is full of suffering,it is also full of overcoming it.

問題描述

小明的實驗室有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

思路：

• way1
  樹上兩個節點之間加了一條邊，使樹形成了一個環。
  要找到這個環，如果知道環上的兩點，環的路徑就更容易確定，所以首先會想到并查集。先用并查集來確定環上的兩個點，一個作為起點和一個終點,然后dfs記錄路徑即可。

• way2

  把握住樹上節點度的特點，不在環上的節點度必為1，
  所以可以使用拓撲排序，不斷刪除與度為1節點相連的邊，
  最終剩下的節點（度>1）即為環上的點。

代碼：

way1：并查集+dfs

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5+5; struct Edge {int from;int to;int next; } edge[N<<1]; int head[N],id; bool vis[N]; int pre[N]; int s,e; int k; inline void add_edge(int from,int to) {//edge[id].from = from;edge[id].to = to;edge[id].next = head[from];head[from] = id++; } void init() {memset(head,-1,sizeof(head));id = 0; } int myFind(int x) {if(pre[x] == x)return x;return pre[x] = myFind(pre[x]); }int myUnion(int x,int y) {int fx = myFind(x);int fy = myFind(y);if(fx != fy){pre[fx] = fy;return 0;}return 1; }void dfs(int u,int cnt) {for(int i = head[u]; ~i; i = edge[i].next){int to = edge[i].to;if(!vis[to]){vis[to] = true;pre[cnt+1] = to;dfs(to,cnt+1);}else if(to == e && u != s)//保證不會一開始就走終點，而是走一圈{pre[++cnt] = e;sort(pre,pre+cnt+1);printf("%d",pre[0]);for(int i = 1; i <= cnt; i++){printf(" %d",pre[i]);}cnt--;return;}} } int main() {int n;scanf("%d",&n);for(int i = 1; i <= n; i++){pre[i] = i;}init();bool flag = 0;while(n--){int x,y;scanf("%d%d",&x,&y);if(!flag){flag = myUnion(x,y);s = x;e = y;}add_edge(x,y);add_edge(y,x);}vis[s] = true;vis[e] = true;pre[0] = s;dfs(s,0);return 0; }

way2:拓撲序

#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int N = 1e5+5; int d[N]; struct Edge {int from;int to;int next; }edge[N<<1]; int head[N],id; void init() {memset(head,-1,sizeof(head));id = 0; } inline void add_edge(int from,int to) {edge[id].from = from;edge[id].to = to;edge[id].next = head[from];head[from] = id++; }void topSort(int n) {queue<int>q;for(int i = 1; i <= n; i++){if(d[i] == 1){q.push(i);}}while(!q.empty()){int u = q.front();d[u]--;q.pop();for(int i = head[u]; ~i; i = edge[i].next){int to = edge[i].to;d[to]--;if(d[to] == 1){q.push(to);}}}for(int i = 1; i <= n; i++){if(d[i] > 1){printf("%d ",i);}}puts(""); } int main() {int n;scanf("%d",&n);init();for(int i = 0; i < n; i++){int x,y;scanf("%d%d",&x,&y);d[x]++,d[y]++;add_edge(x,y);add_edge(y,x);}topSort(n);return 0; }

總結

以上是生活随笔為你收集整理的历届试题 发现环的全部內容，希望文章能夠幫你解決所遇到的問題。

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