并查集+DFS求树上成环的点
问题描述 小明的实验室有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
#include <bits/stdc++.h> #include <string.h> #include <vector> #include <algorithm> using namespace std; const int maxn = 100000+5; int par[maxn], vis[maxn], ret[maxn]; vector<int> edge[maxn]; int n, s, f; int finds(int x) { return x==par[x]?x:par[x]=finds(par[x]); } void dfs(int x,int id) { ret[id]=x; if(x==f) { sort(ret,ret+id+1); for(int i=0; i<=id; i++) cout<<ret[i]<<" "; cout<<endl; return ; } for(int i=0; i<edge[x].size(); i++) { int v=edge[x][i]; if(vis[v]) continue; vis[v]=1; dfs(v,id+1); vis[v]=0; } } int main() { int n; while(cin>>n) { memset(ret,0,sizeof(ret)); memset(edge,0,sizeof(edge)); for(int i=1; i<=n; i++) par[i]=i; for(int i=1; i<=n; i++) { int a,b; cin>>a>>b; int fa=finds(a); int fb=finds(b); if(fa!=fb) { par[fa]=fb; edge[a].push_back(b); edge[b].push_back(a); } else { s=a; f=b; } } vis[s]=1; dfs(s,0); } }
