题目大意就是说有n只猫，摆放成一行，就是构成了一个n的排列，然后告诉你n-1次的操作（操作就是给x和y，然后把x对应房间和y对应房间的墙拆掉合并为一个房间），这n-1次操作执行完后，n只猫在一个房间里，要你求这个排列。
做法就是一开始把每只猫想象成在一个链表里，如果x和y猫所在房间要合并的话就把x所在链表的尾和y所在链表的头连接即可（x连到y上也是可以的），一旦连接更新下nxt值即可，然后找一只猫所在链表的头和尾的话就用并查集的思想做。
#include<bits/stdc++.h>
using namespace std;
const int maxn=150010;
struct node
{
int h,t,nxt;
}lst[maxn];
inline int findh(int x)
{
return (x!=lst[x].h)?lst[x].h=findh(lst[x].h):x;
}
inline int findt(int x)
{
return (x!=lst[x].t)?lst[x].t=findt(lst[x].t):x;
}
inline void merge(int x,int y)
{
int tx=findt(x),hy=findh(y);
lst[tx].nxt=hy;
lst[tx].t=findt(y);
lst[hy].h=findh(x);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) lst[i].h=lst[i].t=i;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
merge(x,y);
}
int now=findh(1);
for(;now;now=lst[now].nxt)
printf("%d ",now);
return 0;
}