所以问题来了，第一：对于合并3,1我怎么知道是要合并3和1,4，而不是只合并3和1，把4抛弃？这时就要用到并查集，我们可以写一个并查集，查什么呢？当然是查??在哪个隔间，然后把两个隔间合并。第二：这个好像只是模拟这个过程啊，怎样保存结果？其中一种做法就是给隔间分配额外的编号，把这个树（记得存树是存树的编号）存下来，然后用递归遍历一次就可以输出结果了（记得这时并查集查的是隔间的编号）。树：
1 #include <bits/stdc++.h> //万能头文件 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 <bits/stdc++.h> //万能头文件 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的末尾一个元素接y 27 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 }
Codeforces Round #541 F. Asya And Kittens
原文：https://www.cnblogs.com/happy-MEdge/p/10775905.html