历届试题 发现环
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
Input
第一行包含一个整数N。 以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。
对于30%的数据，1 <= N <= 1000 对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N
输入保证合法。
Output
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
Examples
样例输入 5 1 2 3 1 2 4 2 5 5 3 样例输出 1 2 3 5
Hint
题意:
题解:
比较经典的图中判环问题, 通过DFS来搜, 储存每个节点的父节点, 发现有已访问的节点且不为当前节点父节点, 就说明出现了环, 顺着查找pre数组即可 因为只有一个环, 所以复杂度O(N)
经验小结:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std
;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL
;
const int inf
= 1<<30;
const LL maxn
= 1e5+10;
int N
;
vector
<int> es
[maxn
], ans
;
bool vis
[maxn
];
int pre
[maxn
];
bool isEnd
= false;
void Dfs(int u
){
vis
[u
] = true;
for(int i
= 0; i
< es
[u
].size(); ++i
){
if(isEnd
) return;
int v
= es
[u
][i
];
if(!vis
[v
]){
pre
[v
] = u
;
Dfs(v
);
}
else if(pre
[u
] != v
){
ans
.push_back(v
);
while(v
!= u
){
ans
.push_back(u
);
u
= pre
[u
];
}
sort(ans
.begin(), ans
.end());
for(int i
= 0; i
< ans
.size(); ++i
)
cout
<< ans
[i
] << " ";
cout
<< endl
;
isEnd
= true;
return;
}
}
}
int main()
{
int a
, b
;
cin
>> N
;
for(int i
= 1; i
<= N
; ++i
){
cin
>> a
>> b
;
es
[a
].push_back(b
), es
[b
].push_back(a
);
}
ms(pre
, -1);
Dfs(1);
return 0;
}
