小明的实验室有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
思路：bfs+并查集
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<set> #include<vector> #include<cmath> const int maxn=1e6+5; typedef long long ll; using namespace std; int n , head[maxn],net[maxn<<1],u[maxn<<1],v[maxn<<1],d[maxn],cnt=1; int q[maxn],f[maxn],du[maxn],tot; ll g[maxn]; void add(int x,int y,int z) { u[++cnt] = y , d[cnt] = z , net[cnt] = head[x] , head[x] = cnt; ++du[y]; } void bfs(int x) { int y , l , r , now; l = r = 1; q[1] = x ; while (l <= r) { now = q[l] , ++l , --du[now]; for (int i = head[now] ; i ; i = net[i]) { if (du[y = u[i]] > 1) { if (--du[y] == 1) q[++r] = y; } } } } void find_hoop(int x) { int l , r , now , y; l = r = 1 , q[1] = x; f[++tot] = x ; while (l <= r) { now = q[l] , ++l; for (int i = head[now] ; i ; i = net[i]) { if (du[y = u[i]] && !v[i]) { v[i] = v[i^1] = 1; f[++tot] = y; g[tot] = g[tot - 1] + d[i]; q[++r] = y; break; } } } } int main() { scanf("%d" , &n); for (int i = 1 ; i <= n ; ++i) { int a , b , c; scanf("%d%d" , &a , &b ); add(a , b , 1) , add(b , a , 1); } for (int i = 1 ; i <= n ; ++i) { if (du[i] == 1) bfs(i); } for (int i = 1 ; i <= n ; ++i) { if (du[i]) { find_hoop(i); for (int j = 1 ; j <= tot ; ++j) { du[f[j]] = 0; } } } sort(f+1,f+tot); for (int i = 1 ; i < tot ; ++i) { printf ("%d " , f[i]); } return 0; }