题目链接：http://lx.lanqiao.cn/problem.page?gpid=T453
问题描述
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入格式
第一行包含一个整数N。
以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。
以下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 1
2 4
2 5
5 3
样例输出
1 2 3 5
解题思路：第一种解法是用拓扑排序的方式，把度数为1的点去掉，然后剩下的度数为2的点就是答案了，第二种解法是用并查集找到环上相邻的两个点，然后用dfs一个为起点一个为终点，就可以搜索出答案。
代码：
第一种解法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
int n,tot,head[maxn],in[maxn];
vector<int> ans;
struct node{
int to,next;
}edge[*maxn];
void add(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void topsort(){
queue<int> que;
for(int i=;i<=n;i++){
if(in[i]==)que.push(i);
}
while(que.size()){
int now=que.front();
que.pop();
for(int i=head[now];i!=-;i=edge[i].next){
int v=edge[i].to;
in[v]--;
if(in[v]==)que.push(v);
}
}
for(int i=;i<=n;i++){
if(in[i]==)ans.push_back(i);
}
}
int main(){
cin>>n;
for(int i=;i<=n;i++)head[i]=-;
for(int i=;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
in[u]++; in[v]++;
}
topsort();
sort(ans.begin(),ans.end());
for(int i=;i<ans.size();i++)
{
printf("%d",ans[i]);
if(i!=ans.size()-)cout<<" ";
else cout<<endl;
}
return ;
}
第二种解法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
int n,tot,st,ed,head[maxn],par[maxn],pre[maxn],vis[maxn];
vector<int> ans;
struct node{
int to,next;
}edge[*maxn];
void add(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
int find(int x){
if(x==par[x])return x;
else return par[x]=find(par[x]);
}
void unite(int x,int y){
int fx=find(x),fy=find(y);
par[fx]=fy;
}
void dfs(int x){
vis[x]=;
for(int i=head[x];i!=-;i=edge[i].next){
int v=edge[i].to;
if(!vis[v]){
if(x==st&&v==ed)continue;
vis[v]=;
pre[v]=x;
if(v==ed)return;
dfs(v);
}
}
}
int main(){
cin>>n;
for(int i=;i<=n;i++){
head[i]=-;
par[i]=i;
}
for(int i=;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
if(find(u)!=find(v))unite(u,v);
else{
st=u;
ed=v;
}
}
pre[st]=st;
dfs(st);
int tmp=ed;
ans.push_back(ed);
while(pre[tmp]!=tmp){
tmp=pre[tmp];
ans.push_back(tmp);
}
sort(ans.begin(),ans.end());
for(int i=;i<ans.size();i++)
{
printf("%d",ans[i]);
if(i!=ans.size()-)cout<<" ";
else cout<<endl;
}
return ;
}