发现环

问题描述

　　小明的实验室有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

Algorithm

这个题目做了很长时间了，因为之前学习了并查集寻找环，因此首先用并查集寻找是否有环（当然这里肯定是有的...）

我们主要目的是找到环上的两个点，从这两个点中的一个出发，回到另一个点，那么这就是我们想要找的环了。

虽说题目讲的是树状结构，但是也是图的一种特殊情况，我们可以直接用图的遍历来搜索这个环。

我不知道这两种方法那种更节约时间，直观看来应该相差不多。

无论怎样，我们都需要构图，这里用邻接表的数据结构好一点（稀疏图与稠密图），动态数组就可以完成。

备注：这串代码调试了很久，不知道为什么有时候会返回一个错误的返回值，应该是我哪里写错了，最有可能的就是在vector的使用的地方。

遗憾的是我没有找出来，只能得90分。但是算法本身并没错。

当我将上面的数据

输入时，正确输出！然后再输入，就会返回一个错误的value。

反之，先输入下面的数据，再输入上面的数据，那么下面的会正确输出。

AC

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<vector>
  4 #include<algorithm>
  5 #include<cstring>
  6 
  7 using namespace std;
  8 
  9 const int MAX_V = 100009;
 10 int par[MAX_V] = {0};
 11 int rank[MAX_V];     // 树的高度
 12 vector<int> G[MAX_V];
 13 vector<int> step, V;
 14 bool flag[MAX_V];
 15 int N = 0; 
 16 
 17 // 初始化 
 18 void Init(int n)
 19 {
 20     memset(rank, 0, sizeof(rank));
 21     for(int i=0;i<MAX_V;i++)
 22         par[i] = i;
 23 }
 24 
 25 // 查找 
 26 int find_root(int x)
 27 {
 28     // 用了递归压缩之后通过了 90% 的数据...
 29     // while循环只通过了 30% ... 
 30     return par[x] == x?x:par[x] = find_root(par[x]);
 31 }
 32 
 33 // 合并 
 34 bool merge(int x, int y)
 35 {
 36     x = find_root(x);
 37     y = find_root(y);
 38     if(x == y) return false;
 39     if(rank[x] == rank[y]){
 40         par[x] = y;
 41     }
 42     else{
 43         par[y] = x;
 44         if(rank[x] == rank[y]) rank[x]++;
 45     }
 46     return true;
 47 }
 48 
 49 void print()
 50 {
 51     for(int i=0;i<V.size();i++)
 52         cout<<V.at(i)<<" ";
 53     cout<<'
';
 54     vector<int>().swap(V);
 55     // V.swap(vector<int>());
 56     return;
 57  } 
 58 
 59 void dfs(int a, int b)
 60 {
 61     if(G[b].size() == 0) return;
 62     if(b == a){ // a, b是环上的两个点,从b出发回到a为一个环 
 63         sort(step.begin(), step.end());
 64         for(int i=0;i<step.size();i++)
 65             V.push_back(step.at(i));
 66         for(int i=1;i<N+1;i++)
 67             G[i].clear();
 68         step.clear();
 69         return;
 70     }
 71     for(int i=0;i<G[b].size();i++){
 72         if(!flag[G[b].at(i)])
 73             continue;
 74         step.push_back(G[b].at(i));
 75         flag[b] = false;
 76         dfs(a, G[b].at(i));
 77         flag[b] = true;
 78         step.pop_back();
 79     }
 80     return;
 81 }
 82 
 83 int main()
 84 {
 85     int a, b;
 86     // while(cin>>N)
 87     cin>>N;
 88     {
 89         Init(N+1);
 90         memset(flag, true, sizeof(flag));
 91         while(N--)
 92         {
 93             cin>>a>>b;
 94             G[a].push_back(b);
 95             G[b].push_back(a);
 96             if(!merge(a, b)){
 97                 // cout<<"Already find~"<<endl;
 98 /* 找到环，此时开始搜索能避免多余的点和边，加快搜索速度 */
 99                 G[b].pop_back();     // 终点 pop 掉 
100                 step.push_back(b);    // 起点压入路径 
101                 dfs(a, b);
102             }
103         }
104         print();
105     }
106     
107     return 0;
108 }

View Code

2019-02-12

15:29:55