标题：发现环
小明的实验室有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
资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
思路 ： 并查集 找环 未成环之前 看作一个树 用并查集找到环 两点 找的同时 建立一个 并查集树（自己瞎起的）找到两点后 从两个点分别回到并查集的根节点经过的点标记上 这两个点单独经过的点（交点处除外）都是环上点
*/
代码语言：javascript复制#include<stdio.h>
#include<string.h>
#define N 1000002
typedef long long ll;
ll a[N][3],f[N],bj[N],jd[N];
ll BCJ(ll s)//并查集找根和更新
{ return f[s]==0?s:f[s]=BCJ(f[s]);
}
//ll BCJ(ll s)
//{
// ll tem ,tx=s;
// while(f[tx]!=0)tx=f[tx];//并查集找根
// while(s!=tx)//并查集更新
// { tem=f[s];
// f[s]=tx;
// s=tem;
// }
// return tx;
//}
void BCJtree(ll x1,ll x2)//建立并查集树
{
ll tx=x2,next=x1,last=jd[x1]; //两树合并 父变子 子变父
while(next!=0)
{
jd[next]=tx;
tx=next;
next=last;
last=jd[next];
}
}
void xzh(ll x)//寻找环节点
{ ll last,r=x;bj[x] =1;
while(1)
{if(jd[x]==0||bj[x]==2)break;//到并查集根节点或有重复节点 跳出
last=jd[x];
bj[last] =1;
x=last;
}
if(bj[x]==2)// 重复节点 消重和去多余节点
{ bj[x]=1;
while(jd[x]!=0)
{last=jd[x];
bj[last]=0;
x=last;
}
}
}
int main()
{ ll i,j,s1,s2,n,flag;
while(scanf("%lld",&n)!=EOF)
{ flag=0;
memset(f,0,sizeof(f));
memset(bj,0,sizeof(bj));
memset(jd,0,sizeof(jd));
for(i=1;i<=n;i )
{ scanf("%lld%lld",&a[i][0],&a[i][1]);
if(!flag)
{
s1=BCJ(a[i][0]);
s2=BCJ(a[i][1]);
if(s1==s2)flag=i;//如果之前已经是同集合 这为环上两点 标记
else
{
if(!f[a[i][0]]) f[s1]=s2,BCJtree(a[i][0],a[i][1]);//a[i][0]节点为单集合或作为根节点的集合
else f[s2]=s1,BCJtree(a[i][1],a[i][0]);// 含a[i][1]的集合接在含a[i][0]的集合
}
}
}
xzh(a[flag][0]);//从 A节点开始走
xzh(a[flag][1]);//从 B节点开始走
for(i=1;i<=n;i )
if(bj[i]==1)printf("%lld ",i);
printf("n");
}
return 0;
}
