F. Asya And Kittens（List+并查集）

有 n 只猫，原来分别在一个笼子里，但是相邻的猫想一起玩就将它们放在一个笼子里，但是现在它们凑成了一堆，问他们原来在几号笼子里 

const int N=15*1e4+5;int n,m,t;int i,j,k;int fa[N];list<int> l[N];
int Find(int x)
{return fa[x]==x? x: fa[x]=Find(fa[x]);
}
int main()
{IOS;while(cin>>n){for(i=1;i<=n;i++) fa[i]=i,l[i].pb(i);for(i=1;i<n;i++){int x,y;cin>>x>>y;x=Find(x);y=Find(y);fa[x]=y;l[y].splice(l[y].end(),l[x]);//将 x 节点与节点 y 合并 }int cur=Find(n);for(list<int>::iterator it=l[cur].begin();;it++){if(it==l[cur].end()) break;cout<<*it<<" ";}}//PAUSE;return 0;
}