建议优先阅读可持久化线段树。
可持久化并查集
可持久化并查集，即可撤销并查集，支持回退到之前某个版本信息。
显然需要维护 $f_x$ 为 $x$ 的父节点。使用可持久化线段树维护 $f_x$ 即可。
但是，注意可持久化并查集不能使用路径压缩，只能使用启发式合并优化。否则会破坏历史版本信息。
单次寻找根节点的复杂度为 $\mathcal O(\log n)$。
启发式合并与按秩合并
凑字数的内容。
所谓「启发式合并」，一般多指将大小较小的并查集合并到大小较大的并查集上。而「按秩合并」一般指将深度较小的并查集合并到深度较大的并查集上。
这两种方式最终寻找根节点的复杂度都是 $\mathcal O(\log n)$ 的。
启发式合并在最坏情况下，合并之后大小会翻倍。因为至多翻 $\mathcal O(\log n)$ 倍，故深度至多为 $\mathcal O(\log n)$。
按秩合并的复杂度同样为 $\mathcal O(\log n)$。因为深度为 $k$ 的树至少包含 $2^k$ 个节点。否则为一条链，但是这种情况显然不会在并查集种存在。因此树的深度最大为 $\mathcal O(\log n)$。
实际应用还是建议写启发式合并，因为维护子树大小只需要相加即可，但是维护子树深度可能涉及一些复杂操作。（但是其实也不是很复杂。）
例题 AC 代码
时间复杂度：$\mathcal O\left(m\log^2n\right)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef int (*fp)(int);
constexpr const int N=1e5,M=2e5;
int n;
struct segTree{
int root[M+1],size;
struct node{
int l,r;
int value;
int lChild,rChild;
}t[200*N+1];
segTree(){
size=0;
}
int create(node x){
t[++size]=x;
return size;
}
int clone(int p){
t[++size]=t[p];
return size;
}
int build(int l,int r,fp func){
node x={l,r};
if(l==r){
x.value=func(l);
return create(x);
}
int mid=l+r>>1;
x.lChild=build(l,mid,func);
x.rChild=build(mid+1,r,func);
return create(x);
}
int update(int p,int x,int k){
p=clone(p);
if(t[p].l==t[p].r){
t[p].value=k;
return p;
}
if(x<=t[t[p].lChild].r){
t[p].lChild=update(t[p].lChild,x,k);
}else{
t[p].rChild=update(t[p].rChild,x,k);
}
return p;
}
void update(int v,int i,int x,int k){
root[i]=update(root[v],x,k);
}
int query(int p,int x){
if(t[p].l==t[p].r){
return t[p].value;
}
if(x<=t[t[p].lChild].r){
return query(t[p].lChild,x);
}else{
return query(t[p].rChild,x);
}
}
int query(int v,int i,int x){
root[i]=root[v];
return query(root[i],x);
}
void copy(int v,int i){
root[i]=root[v];
}
};
struct dsu{
segTree f,size;
void build(int n){
f.root[0]=f.build(1,n,[](int x){
return x;
});
size.root[0]=size.build(1,n,[](int x){
return 1;
});
}
int find(int v,int i,int x){
int fx=f.query(v,i,x);
if(fx!=x){
return find(v,i,fx);
}else{
return x;
}
}
void cancel(int v,int i){
f.copy(v,i);
size.copy(v,i);
}
void merge(int v,int i,int a,int b){
cancel(v,i);
a=find(i,i,a);b=find(i,i,b);
if(a==b){
return;
}
int sizeA=size.query(i,i,a),sizeB=size.query(i,i,b);
if(sizeA<sizeB){
f.update(i,i,a,b);
size.update(i,i,b,sizeA+sizeB);
}else{
f.update(i,i,b,a);
size.update(i,i,a,sizeA+sizeB);
}
}
}dsu;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
dsu.build(n);
for(int i=1;i<=m;i++){
int opt,k,a,b;
cin>>opt;
switch(opt){
case 1:
cin>>a>>b;
dsu.merge(i-1,i,a,b);
break;
case 2:
cin>>k;
dsu.cancel(k,i);
break;
case 3:
cin>>a>>b;
dsu.cancel(i-1,i);
cout<<(dsu.find(i,i,a)==dsu.find(i,i,b))<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
