codeforces 构造 Asya And Kittens

题目描述：

算法：并查集

        使用两个并查集vl, vr分别记录当前集合的最左元素和最右元素，在合并时将记录最左元素的根节点接在左侧集合的根节点下，记录右侧的接在右侧根节点下即vr[ar] = br, vl[bl] = al，ar, br为两个集合的根节点。
        在拼接过程中再记录拼接点的左右元素分别是谁，即r[ar] = bl, l[bl] = ar。
        最后找到最左节点通过r数组遍历输出即可。

        此处参考了这篇博文

        

        int al = find(vl, a), ar = find(vr, a);
        int bl = find(vl, b), br = find(vr, b);

        r[ar] = bl, l[bl] = ar; //为拼接点记录左右节点

        首先我们看这里，对于输入的 a 和 b , 我们找到这两个集合的左右边界，随后我们只修改ar 和 bl的 l 和 r 数组，我们默认 a 集合在 左侧， b 集合在右侧。如 {al .... a..... ar} 和集合 { bl.....b.....br},我们仅修改 ar 和 bl 的 l 或 r 数组，也就意味着，中间那块 l 和 r 数组是不变的，相当于通过ar， bl 向外扩散。而我们先找到最左边的元素，然后不断用 r 数组，就相当于一个抽丝剥茧的逆过程。不知道我想得对不对。

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include <numeric>
#include <string>
#define ll long long 
#include<set>
#include<bitset>vector<int> vl; vector<int> vr;
vector<int> l; vector<int> r;int find(vector<int>& a, int x) {if (a[x] == x) return x;a[x] = find(a,a[x]);return a[x];
}int main() {int n; cin >> n;vl.resize(n + 1); vr.resize(n + 1); l.resize(n + 1); r.resize(n + 1);for (int i = 1; i <= n; i++)vl[i] = vr[i] = l[i] = r[i] = i;// vl 和 vr 表示的是一个集合中最左端和最右端的位置，其中root节点为最左端或者最右端// l 和 r 表示的是 某个节点的最左或是最右端的父节点for (int i = 1; i < n; i++){int a, b;cin >> a >> b;int al = find(vl, a), ar = find(vr, a);int bl = find(vl, b), br = find(vr, b);//  al     a    ar/bl   b    br//  bl     b    br/al   a    arr[ar] = bl, l[bl] = ar; //为拼接点记录左右节点vr[ar] = br, vl[bl] = al; //合并集合}int k = find(l, 1); //最左节点for (int j = 1; j <= n; j++){cout << k << " ";k = r[k];}cout << endl;return 0;
}