这一类并查集与普通并查集的不同之处在于：find 函数中不再使用路径压缩，而是单纯使用启发式合并的方法合并两个集合（小 \(\rightarrow\) 大）。这样做虽然使得每次 find 从 \(O(1)\) 退化到了 \(O(\log n)\)，但做撤销操作会极其方便：每次撤销只需要修改一个点的 fa 和 siz 的信息（若存在路径压缩，则可能需要恢复很多个点的信息）。
可撤销并查集
只需要多维护一个栈，存放之前做过的所有合并操作；
- 每次合并操作需要入栈，存放信息可以自己设定，一般均需包含（大集合祖先结点，小集合祖先结点）。
- 当需要撤销时直接根据栈顶恢复原信息并弹栈即可。
例题：
ABC302 H
每个小球用一个结点表示（不同于树中的点），则每到一个树中的点，就将该点中的两个小球所代表结点连边，表示这两个小球中可以选其中一个。
分析每个集合（大小为 \(n\)）可选小球数量与图结构的关系：
- 若该集合满足边数 \(=\) 点数 \(-1\)（即一棵树），则该集合内可以选择 \(n-1\) 个小球。
- 否则，一定有边数 \(\geq\) 点数。由于可选小球最多就只有 \(n\) 个，因此这种情况下最多可以选择 \(n\) 个小球。
每次合并对答案的影响：需要对两个结点所在集合的边数与点数之间关系进行分类讨论。假设当前合并的两个结点是 \(x, y\)：
- 两个点不在同一个集合：
- 两个结点所在集合均满足点数 \(\leq\) 边数：说明此时两个集合内都没有空闲点选择。此时将两个集合连边，并不会增加答案。
- 两个结点所在集合存在某一个集合满足边数 \(=\) 点数 \(-1\)：此时该集合存在未选择的小球，那么新增的两个集合之间的连边就可以分配给那个空闲的小球，答案会增加 \(1\)。
- 两个点在同一个集合：
- 该集合满足边数 \(=\) 点数 \(-1\)：此时存在一个未选择的小球，新增连边会被分配到这个小球，答案增加 \(1\)。
- 该集合满足边数 \(\geq\) 点数： 此时不存在未选择的小球，答案不变。
更多实现细节见 code 部分。
code
CF891C
首先需要清楚有关 Kruskal 生成树的一个小结论：众所周知 Kruskal 按照边权大小升序，并根据两个端点的连通性决策每一条边是否选择。那么，对于所有权值相同的边，在Kruskal算法中它们内部的决策顺序不会影响 考虑所有该边权的边后 整个图的连通性（否则在该权值的所有边的内部也应当存在一个最优选择顺序，违背了 Kruskal 算法原理）。
那么，对于每一个询问，我们可以按升序每次检验权值相同的边集（即边权等于 \(X\) 的所有边，所有 \(<X\) 的边都已考虑，边权 \(\geq X\) 的边均未考虑），如果这些边都能按照 Kruskal 算法加入到正在生成的 MST 中，就说明这些边一定可以在同一棵 MST 中；否则就一定不行。以后再考虑边权 \(Y（> X）\) 时，就无需再考虑小于 \(Y\) 的所有边权，因为由上一段中的结论，在 Kruskal 算法流程考虑完所有 \(<Y\) 的边权后，无论前面的选择方案如何，当前整个图中任意两点的连通性是固定的（类似于递推性，前面均已合法就继续考虑后面，无需在意前面的影响）
那么对于多个询问，我们就可以按照边权大小升序排序并进行离线处理，每次处理某一个询问中边权相同的所有边。而不同询问之间是相互独立的，而检验过程需要将边加入到并查集里，因此在处理某个相同边权的不同问题的询问时，我们需要将处理上一个问题时加入到并查集中的所有边删除，因此需要用可撤销并查集。
具体实现见 code。
code
CF1444C
首先解决一个问题：对于一个由某些人组成的组，组中存在若干对矛盾关系，那么我们如何去判断这个组是否最多可以划分成两个子集，每个人一定属于某个子集，并且每个子集内的人两两之间无矛盾？显然将所有人看作结点，所有矛盾关系看作边，可行的充要条件即整个图是一个二分图。
因为下面需要用到可撤销并查集来解决后续问题，所以这里采用 扩展域并查集判断二分图 的方式：由于最多只能划分成两个集合，因此将每个人划分成两种（eg: 第一个人划分成 \(1\) 和 \(1'\) 两种，分别表示其在第一个集合/第二个集合），于是并查集中就有 \(2n\) 个对象。假设第二个人和第三个人之间存在矛盾，那么我们就将 \(2\) 与 \(3'\)、\(3\) 与 \(2'\) 合并，表示它们必须同时成立。那么一旦处理某个矛盾关系 \((a,b)\) 时，发现 \(a\) 与 \(b\) 在同一个集合中，说明这两个人必须划分到同一个集合，与该矛盾关系冲突，那么这个组本身就不可被划分成最多两个集合，更不用提其与另一个组的人结合再判断，因此这样的组直接丢弃就好。最终处理出所有内部可划分的组。
将全部的 \(m\) 条边划分为两类：
- 连接的两点属于同一组
- 连接的两点属于不同组
对于第一种边，只代表了组内成员之间的矛盾，我们刚才已经处理过了，且处理过的关系仍在并查集中体现。现在我们需要处理第二种边，检查出所有不能划分成两个集合的组对：将第二种边按照连接的人所属的组划分（连接的两个人构成的组对相同的边划分到同一划分）。每一种划分只需要检验这个组对是否可构成一个二分图，检验方式和上面的类似。而我们需要处理多种划分，因此每处理完一种划分，我们需要删除刚刚添加的组对关系，只留下原来的组间关系，以便后续的处理，这便是用到可撤销并查集的地方。
实现见 code。
code
可持久化并查集
相当于对 fa 和 siz 数组作可持久化，维护每一个前缀的版本。
模板：
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
//#define int long long
typedef long long ll;
typedef __int128 LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;int n, m;
const int maxn = 2e5 + 10;
int root_fa[maxn], root_siz[maxn], ls[maxn * 40], rs[maxn * 40], val[maxn * 40], tot;int build_fa(int nl, int nr){int u = ++tot;if(nl == nr){val[u] = nl;}else{int mid = nl + nr >> 1;ls[u] = build_fa(nl, mid);rs[u] = build_fa(mid + 1, nr);}return u;
}int build_siz(int nl, int nr){int u = ++tot;if(nl == nr){val[u] = 1;}else{int mid = nl + nr >> 1;ls[u] = build_siz(nl, mid);rs[u] = build_siz(mid + 1, nr);}return u;
}int update(int u, int nl, int nr, int pos, int v){int rt = ++tot;ls[rt] = ls[u];rs[rt] = rs[u];if(nl == nr){val[rt] = v;}else{int mid = nl + nr >> 1;if(pos <= mid){ls[rt] = update(ls[rt], nl, mid, pos, v);}else{rs[rt] = update(rs[rt], mid + 1, nr, pos, v);}}return rt;
}int query(int u, int nl, int nr, int pos){if(nl == nr){return val[u];}int mid = nl + nr >> 1;if(pos <= mid) return query(ls[u], nl, mid, pos);else return query(rs[u], mid + 1, nr, pos);
}int find(int x, int v){ // 在 v 版本中查询 x 集合的祖先int fa = query(root_fa[v], 1, n, x);while(x != fa){x = fa;fa = query(root_fa[v], 1, n, x);}return x;
}void union_(int x, int y, int v){ // 在 v 版本中合并 x, y 所在的两个集合int ancx = find(x, v);int ancy = find(y, v);if(ancx != ancy){int xsiz = query(root_siz[v], 1, n, ancx);int ysiz = query(root_siz[v], 1, n, ancy);if(xsiz >= ysiz){ // 将 y 集合合并到 x 集合// fa[y] = x, siz[x] += siz[y]root_fa[v] = update(root_fa[v], 1, n, ancy, ancx);root_siz[v] = update(root_siz[v], 1, n, ancx, xsiz + ysiz); }else{// fa[x] = y, siz[y] += siz[x]root_fa[v] = update(root_fa[v], 1, n, ancx, ancy);root_siz[v] = update(root_siz[v], 1, n, ancy, xsiz + ysiz); }}
}// P3402
void solve()
{cin >> n >> m;root_fa[0] = build_fa(1, n);root_siz[0] = build_siz(1, n);int a, b, k;for(int i = 1; i <= m; i ++){int op; cin >> op;root_fa[i] = root_fa[i - 1];root_siz[i] = root_siz[i - 1];if(op == 1){ // 在上一个版本的基础上，合并 a, b 所在集合cin >> a >> b;union_(a, b, i);}if(op == 2){ // 回到第k个版本cin >> k;root_fa[i] = root_fa[k];root_siz[i] = root_siz[k];}if(op == 3){ // 查询在当前版本下，a, b 是否属于同一个集合cin >> a >> b;cout << (find(a, i) == find(b, i)) << "\n";}}
}signed main()
{
// freopen("in.txt", "rt", stdin);
// freopen("out.txt", "wt", stdout);ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);// int T=1; cin>>T; while(T--)solve();return 0;
}