可持久化并查集
#include <iostream>
#include <cstdio>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int MAXN = 2e4 + 5;
const int MAXM = 2e4 + 5;
rope<int> *rp[MAXM];
int find(int i, int x)
{
if(rp[i]->at(x) == x)
{
return x;
}
int fa = find(i, rp[i]->at(x));
if(fa == rp[i]->at(x)) return fa;
rp[i]->replace(x, fa);
return fa;
}
void merge(int i, int x, int y)
{
int fx = find(i, x), fy = find(i, y);
if(fx != fy) rp[i]->replace(fy, fx);
}
bool same(int i, int x, int y)
{
return find(i, x) == find(i, y);
}
int a[MAXN];
int main()
{
int m, n;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) a[i] = i;
rp[0] = new rope<int>(a, a + n + 1);
for(int i = 1; i <= m; ++i)
{
rp[i] = new rope<int>(*rp[i - 1]);
int x;
scanf("%d", &x);
if(x == 1)
{
int a, b;
scanf("%d%d", &a, &b);
merge(i, a, b);
}
if(x == 2)
{
int k;
scanf("%d", &k);
rp[i] = rp[k];
}
if(x == 3)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", same(i, a, b));
}
}
return 0;
}