题目链接：http://codeforces.com/contest/1131/problem/F
思路：
很容易看出这是一道并查集的题目，因为要输出每个cage中住的鸟的编号，故采用静态链表。用l[i]表示一条链的最左端编号，r[i]表示一条链最右端编号，nex[i]表示编号i后面的鸟的编号，root[i]表示i的祖先，剩下套并查集模板即可。我在这CE了两次，后来问了大神才找到错误，bits/stdc++中已经1定义了get，next，而我的程序中将这两个作为变量，从而CE，但可能是我的编译器的标准库的问题，使得本地可以通过。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=150005; 5 int n,x,y; 6 int l[maxn],r[maxn],nex[maxn],root[maxn]; 7 8 int getr(int k){ 9 if(root[k]==k) return k; 10 else return root[k]=getr(root[k]); 11 } 12 13 int main(){ 14 scanf("%d",&n); 15 for(int i=1;i<=n;++i) 16 l[i]=i,r[i]=i,root[i]=i; 17 n--; 18 while(n--){ 19 scanf("%d%d",&x,&y); 20 int rx=getr(x),ry=getr(y); 21 root[ry]=rx; 22 nex[r[rx]]=l[ry]; 23 r[rx]=r[ry]; 24 } 25 int p=l[get(1)]; 26 while(p){ 27 printf("%d ",p); 28 p=nex[p]; 29 } 30 printf("\n"); 31 return 0; 32 }
原文：https://www.cnblogs.com/FrankChen831X/p/10424971.html