问题描述

　　小明的实验室有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
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              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
            
              G[MAX_V]; 13 vector
             
               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
              

().swap(V); 55 // V.swap(vector

()); 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

>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~"<

 

2019-02-12

15:29:55