题面：
题目描述：
Asya把N只?（从1-N编号）放到笼子里面，笼子是由一行N个隔间组成。两个相邻的隔间有一个隔板。
Asya每天观察到有一对?想一起玩，然后就会把相邻的隔间中的隔板取出来，使两个相邻的隔间合并为一个隔间。
过了N-1天后，所有隔板将被取出，然后所有的隔间合并成一个隔间。
现在Asya记得每天想一起玩的?的编号，要求：?在最开始（笼子的所有隔板未取出前）隔间的位置。如果有多种可能，输出其中一种。
题目分析：
这道题是一道典型的并查集，我们还是先分析一下样例。
首先，?1和?4想一起玩，所以这两只小鸡肯定一开始要放在相邻的隔间，然后合并成一个隔间，也就是这样：
2和5同理：
那么，接下来的3和1怎么合并呢？我们知道1，4之前合并成一个隔间了，所以只要把3放到1，4旁边就行了，也就是这样（我这里为了方便3放到了14的左边，其实左右没有影响）：
对于4和5的合并，如下图：
所以问题来了，第一：对于合并3,1我怎么知道是要合并3和1,4，而不是只合并3和1，把4抛弃？这时就要用到并查集，我们可以写一个并查集，查什么呢？当然是查?在哪个隔间，然后把两个隔间合并。第二：这个好像只是模拟这个过程啊，怎样保存结果？其中一种做法就是给隔间分配额外的编号，把这个树（记得存树是存树的编号）存下来，然后用递归遍历一次就可以输出结果了（记得这时并查集查的是隔间的编号）。树：
AC代码：
1 #include//万能头文件 2 using namespace std; 3 const int maxn = 150000 + 5; 4 int n; 5 int sets[2*maxn], L_node[2*maxn], R_node[2*maxn]; 6 7 int F(int x){ //查 8 if(sets[x] == x || !sets[x]) return x; 9 return sets[x] = F(sets[x]);10 }11 12 void print(int x){ //输出答案13 if(x <= n) printf("%d ", x);14 else {15 print(L_node[x]);16 print(R_node[x]);17 }18 }19 20 int main(){21 cin >> n;22 int id = n; //隔间编号23 int x, y;24 for(int i = 0; i < n-1; i++){25 scanf("%d%d", &x, &y);26 x = F(x); //查27 y = F(y); 28 sets[x] = sets[y] = ++id; //并29 L_node[id] = x; //记录在哪个隔间30 R_node[id] = y; 31 }32 print(id);33 return 0;34 }
大佬的代码：（好像用数组模拟链表实现）
1 #include//万能头文件 2 using namespace std; 3 const int maxn = 150000 + 5; 4 int n; 5 int sets[maxn], G[maxn], last[maxn]; 6 7 int F(int x){ //查 8 if(sets[x] == x) return x; 9 return sets[x] = F(sets[x]);10 }11 12 int main(){13 cin >> n;14 int x, y;15 16 //初始化17 for(int i = 1; i <= n; i++){18 sets[i] = i;19 last[i] = i;20 }21 22 for(int i = 0; i < n-1; i++){23 scanf("%d%d", &x, &y);24 x = F(x); 25 y = F(y); 26 G[last[x]] = y; //x的末尾一个元素接y27 last[x] = last[y]; //x的末尾一个元素更新为y的末尾一个元素28 sets[y] = x; //并, 且x为代表元29 }30 31 for(int i = F(1); i; i = G[i]){32 scanf("%d ", i);33 }34 return 0;35 }