可持久化并查集：一片森林为何只需一个根？

可持久化并查集标题里的“根”，到底是哪个根？是并查集森林里每棵树的根，还是可持久化线段树的根？如果不把这两个“根”分开，很多人在学习这个算法时，会先被字面意思绕晕。

先说结论：可持久化并查集并没有想象中那么难。它本质上就是“可持久化数组 + 按秩合并的并查集”。真正难住大多数人的，不是并查集本身，而是“版本”和“根”之间的关系。你把一棵可持久化线段树的根节点保存下来，就等于保存了整个版本的并查集状态；哪怕并查集内部有一片森林，外部也只需要一个根节点来索引它。

这篇文章会把通常做成动画演示的过程，拆解成一张张“关键帧”来讲。目标是让零基础读者也能照着实现一遍，并且搞清楚三个问题：为什么要可持久化？为什么不能用路径压缩？为什么一片森林只需要保存一个根？

1. 并查集的本质：维护集合的“森林”

1.1 并查集到底在维护什么

并查集（Disjoint Set Union，简称 DSU）解决的是“集合合并”和“元素归类”两类问题。比如有 5 个人，初始每个人自成一个集合；某次操作让 1 号和 2 号成为朋友，那么“1 和 2 在同一个集合里”这个事实要被记录下来；再让 3 号和 4 号成为朋友，又产生一个新集合。

并查集使用两个核心操作：

• find(x)：找到元素 x 所在集合的代表元素（也叫根）。
• merge(x, y)：把 x 所在集合和 y 所在集合合并成一个集合。

这里的“根”是第一个重要概念。每个集合被组织成一棵树，树的根就是集合代表元素。find(x)就是不断沿着父指针向上走，直到走到某个节点的父指针指向自己。

1.2 森林是怎么形成的

先看一个最简单的例子。初始时，每个节点都是独立的根节点：

1 2 3 4 5

执行merge(1, 2)，让 1 的父指针指向 2，并以 2 作为集合代表：

1 -> 2 3 4 5

此时有两个根节点：2 单独是一棵树的根，3、4、5 也各是一棵树的根。多个根节点并存，这就是“树组成森林”的来源。

如果我们再执行merge(3, 4)，树变成：

1 -> 2 3 -> 4 5

此时森林里依然有多棵互不相交的树。所以“并查集 + 森林”是一个天然的组合：并查集内部并不是一棵树，而是多棵树。

1.3 路径压缩和按秩合并，各自解决了什么

原始并查集有两套优化手段。

路径压缩：在find(x)的过程中，把沿途经过的节点直接挂到根节点下面。这样下次再查这些节点时，走的路径会非常短。

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

按秩合并：在合并时，把“树高更低”或者“子树规模更小”的树，接到另一棵树的根上，避免树变成一条长链。

void merge(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return; if (sz[rx] > sz[ry]) swap(rx, ry); fa[rx] = ry; sz[ry] += sz[rx]; }

在普通并查集里，这两个优化可以同时使用，效果也很好。但一旦进入“可持久化”的语境，路径压缩就会变成一个麻烦。这一点在后面第 3 章会重点解释。

2. 可持久化：从“当前状态”到“版本管理”

2.1 为什么要可持久化

普通并查集只维护“当前状态”。每一次合并都会把之前的父指针覆盖掉。如果需要回答“第 k 次操作之后，x 和 y 是否连通”，普通并查集就做不到了，因为第 k 次操作时的状态已经被后面的操作覆盖。

这类问题并不罕见。文本编辑器的撤销、代码分支管理、数据库的整体快照，都有类似需求。算法竞赛中常见的表述是：

• 操作基于某个历史版本执行；
• 查询某个历史版本中两个元素是否连通；
• “回到第 k 次操作后的状态”。

要支持这些操作，就需要让数据结构具备“版本”属性：每次修改产生一个新版本，历史版本不丢失，且不把原有数据复制一遍。

2.2 可持久化数组的本质

可持久化并查集的底层不是“并查集本身”，而是一个可持久化数组——通常用可持久化线段树实现。

可持久化线段树的思想很朴素：每次修改一个位置时，不直接改动原来的节点，而是从根到叶子，复制出一条路径，在这条复制出来的路径上做修改，其他分支继续复用原版本。

举个例子。假设父数组初始是：

下标: 1 2 3 4 5 取值: 1 2 3 4 5

把下标 1 的值改成 2。理论上，新数组是这样：

下标: 1 2 3 4 5 取值: 2 2 3 4 5

如果保存两个完整的数组，每次修改都是 O(n) 的复制成本，完全不可接受。可持久化线段树的方案是：复制的不是整个数组，而是从根到叶子的一条链。

版本 0： [1] [2] [3] [4] [5] 版本 1： [2] [2] [3] [4] [5] ↑ 只对根到下标 1 这条路径新建节点，其他节点复用版本 0

因此，一次单点修改的时空成本是 O(log n)，而不是 O(n)。这就是可持久化数组的核心价值。

2.3 数据结构的“根”和并查集的“根”不是一回事

在第 1 章里，并查集中的“根”指一棵树的代表元素。而在可持久化线段树中，“根”是整个数据结构版本的入口。

这两个概念容易混淆。标题里的“一片森林，为什么只保存一个根”问的其实是：并查集明明是若干棵树的森林，为什么我们只需要记录一个根节点就够了？

答案是：这个根不是并查集森林里某棵树的根，而是“可持久化线段树版本”的根。通过它，可以查到该版本下任何一个数组位置的值；而并查集森林里的多个树根，都只是这个数组中的普通值。

换句话说：

理解了这个区分，标题的疑问就解开了一大半。

3. 核心问题：为什么一片森林只需保存一个根

3.1 把并查集搬到可持久化数组上

普通并查集需要两个数组：

• fa[x]：记录 x 的父节点；
• sz[x]：记录以 x 为根的树的大小，用于按秩合并。

可持久化版本不直接开两个数组，而是开两棵可持续化线段树：

• 第一棵线段树维护fa数组；
• 第二棵线段树维护sz数组。

每个版本，记录两个根节点：rootFa[ver]和rootSz[ver]。

执行find(x)时，不是在fa数组里直接取fa[x]，而是通过可持久化线段树的单点查询，取出“某个版本下的fa[x]”。

3.2 为什么不能直接使用路径压缩

这是可持久化并查集最容易踩坑的地方。

路径压缩的核心动作是：在find的过程中，把路径上所有节点直接指向根节点。这意味着一句话中可能修改很多个父指针。放在可持久化结构里，每个父指针的修改都是一次update，每次update又会新增 O(log n) 个节点。

路径压缩之后，树高会变得很低，但代价是：

• 一次 find 可能产生 O(m) 次单点修改；
• 每次修改在可持久化线段树中新增 O(log n) 个节点；
• 实现复杂度大幅上升，常数非常大。

标准做法是：放弃路径压缩，只使用按秩合并。

按秩合并保证什么？它保证并查集树的高度始终是 O(log n)。即使没有路径压缩，find的一次向上跳转也最多走 O(log n) 步。每一层跳转再配合线段树的单点查询 O(log n)，总复杂度仍可接受。

所以可持久化并查集的一个经典复杂度结论是：

• find时间复杂度：O(log² n)；
• merge时间复杂度：O(log² n)；
• 每生成一个新版本新增节点数：O(log n)；
• 版本回退：O(1)。

3.3 一次 merge 操作的“动画关键帧”

我们用一组“关键帧”描述一次合并。假设当前是整个版本 0 的初始状态，执行merge(1, 2)。

关键帧一：查询两个元素的根。

find(1) -> 1 find(2) -> 2

关键帧二：按秩合并，决定谁指向谁。两端树大小相同，按代码约定，把 1 的父指针指向 2。

关键帧三：修改fa[1] = 2，生成新的 parent 线段树版本。

版本0 parent: [1, 2, 3, 4, 5] 版本1 parent: [2, 2, 3, 4, 5] ↑ 只有下标 1 被修改

关键帧四：修改sz[2] = sz[2] + sz[1]，生成新的 size 线段树版本。

版本0 size: [1, 1, 1, 1, 1] 版本1 size: [1, 2, 1, 1, 1] ↑ 只有下标 2 被修改

外部只需要记录两个新根：rootFa[1]和rootSz[1]。所有未被修改的位置，新版本和旧版本共享同一批节点。

这就是“可持久化”的直觉：每次操作不是推翻重来，而是“复制一条路径 + 改一个叶子 + 复用其余部分”。

4. 环境准备与数据结构设计

4.1 开发环境

本文代码使用 C++17 编写。不涉及第三方库，在 Linux、macOS、Windows 的任意编译环境都可以运行。推荐至少支持 C++14 的编译器，因为代码中使用了using namespace std和 C++17 特性较少，核心部分在 C++11 标准下也能编译通过。

在评测机上提交时，如果遇到“编译错误”或“未定义引用”，优先检查代码块中是否有不符合当前 C++ 标准的语法。

4.2 数据结构字段说明

实现中需要几个全局数组：

• lc[u]、rc[u]：可持久化线段树节点的左右孩子下标；
• val[u]：当前节点的值，仅叶子节点有意义；
• tot：动态节点分配计数器，从 1 开始递增；
• rootFa[ver]：第 ver 个版本中，fa 数组所对应线段树的根；
• rootSz[ver]：第 ver 个版本中，size 数组所对应线段树的根。

空间估算要特别注意。每次update会沿根到叶子新建一条链，链长是 O(log n)。一次合并需要两次 update，所以最多新增节点数大约是操作次数乘以 O(log n)。因此数组大小通常开到：

const int MAXN = 1e5 + 5; const int MAXM = 2e5 + 5; const int MAXNODE = MAXN * 25 + MAXM * 40;

“25”和“40”是经验系数，不是精确数学公式。如果题目数据范围更大，需要按(n + m) * log n适当放大，再留 10% 到 20% 余量。

5. 可持久化并查集的完整实现

5.1 可持久化数组模板

以下代码实现了可持久化线段树的基础步骤：建立、单点修改、单点查询。

// 文件路径：persistent_array.cpp #include <bits/stdc++.h> using namespace std; const int MAXNODE = 3000000; int lc[MAXNODE], rc[MAXNODE], val[MAXNODE]; int tot = 0; // 建树：数组下标从 l 到 r，初始化成数组 a 中的值 int build(int l, int r, int *a) { int cur = ++tot; if (l == r) { val[cur] = a[l]; return cur; } int mid = (l + r) >> 1; lc[cur] = build(l, mid, a); rc[cur] = build(mid + 1, r, a); return cur; } // 单点修改：在 pre 指向的老版本基础上，把 pos 位置改成 v，返回新节点下标 int update(int pre, int l, int r, int pos, int v) { int cur = ++tot; lc[cur] = lc[pre]; rc[cur] = rc[pre]; val[cur] = val[pre]; if (l == r) { val[cur] = v; return cur; } int mid = (l + r) >> 1; if (pos <= mid) { lc[cur] = update(lc[pre], l, mid, pos, v); } else { rc[cur] = update(rc[pre], mid + 1, r, pos, v); } return cur; } // 单点查询：在根为 rt 的版本中，查询 pos 位置的值 int query(int rt, int l, int r, int pos) { if (l == r) { return val[rt]; } int mid = (l + r) >> 1; if (pos <= mid) { return query(lc[rt], l, mid, pos); } return query(rc[rt], mid + 1, r, pos); }

这三个函数是后续所有版本操作的地基。注意update总是先复制pre节点的左右孩子和值，再沿目标方向递归。递归返回后，当前节点的对应孩子被替换为新子树的根。旧版本pre完全没有被修改。

5.2 可持久化并查集的核心操作

并查集操作在可持久化版本下，不再直接访问fa[x]，而是通过query从版本根中取出值。由于不使用路径压缩，find只需要递归向上找根。

// 文件路径：persistent_dsu.cpp // n 表示元素个数，rootFa[ver] 与 rootSz[ver] 保存版本根 int n, m; int rootFa[MAXM], rootSz[MAXM]; // 在版本 ver 中查找 x 的根 // 这里不使用路径压缩，只做纯向上跳转 int findRoot(int ver, int x) { int f = query(rootFa[ver], 1, n, x); if (f == x) { return x; } return findRoot(ver, f); } // 查询版本 ver 中，根为 x 的集合大小 int getSize(int ver, int x) { return query(rootSz[ver], 1, n, x); } // 在版本 ver 中合并 x 和 y，结果写回 rootFa[ver] 和 rootSz[ver] void mergeSet(int ver, int x, int y) { int rx = findRoot(ver, x); int ry = findRoot(ver, y); if (rx == ry) { return; } int sx = getSize(ver, rx); int sy = getSize(ver, ry); // 按秩合并：size 大的当根 if (sx > sy) { swap(rx, ry); swap(sx, sy); } // 把 rx 的父节点指向 ry int newParentRoot = update(rootFa[ver], 1, n, rx, ry); // 更新 ry 的集合大小 int newSizeRoot = update(rootSz[ver], 1, n, ry, sx + sy); rootFa[ver] = newParentRoot; rootSz[ver] = newSizeRoot; } // 判断版本 ver 中 x 和 y 是否连通 bool isConnected(int ver, int x, int y) { return findRoot(ver, x) == findRoot(ver, y); }

这段代码里最关键的一点是：findRoot传递的ver从外部版本号传入，在递归过程中始终保持同一个版本。它绝不能在递归过程中修改任何值。

5.3 完整主程序示例

下面用一个完整程序演示“基于历史版本操作”的流程。输入格式约定如下：

• 1 a x y：基于版本 a，合并 x 和 y，生成一个新版本。
• 2 a：回到版本 a，生成一个新版本，新版本状态与 a 相同。
• 0 a x y：查询版本 a 中 x 和 y 是否连通，输出 0 或 1。

// 文件路径：main.cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int MAXM = 200005; const int MAXNODE = MAXN * 25 + MAXM * 40; int lc[MAXNODE], rc[MAXNODE], val[MAXNODE]; int tot = 0; int n, m; int rootFa[MAXM], rootSz[MAXM]; int INIT_FA[MAXN], INIT_SZ[MAXN]; // 这里省略 build/update/query 的实现 // 请把 5.1 中的三个函数复制到此处 int findRoot(int ver, int x) { int f = query(rootFa[ver], 1, n, x); if (f == x) return x; return findRoot(ver, f); } int getSize(int ver, int x) { return query(rootSz[ver], 1, n, x); } void mergeSet(int ver, int x, int y) { int rx = findRoot(ver, x); int ry = findRoot(ver, y); if (rx == ry) return; int sx = getSize(ver, rx); int sy = getSize(ver, ry); if (sx > sy) { swap(rx, ry); swap(sx, sy); } int newParentRoot = update(rootFa[ver], 1, n, rx, ry); int newSizeRoot = update(rootSz[ver], 1, n, ry, sx + sy); rootFa[ver] = newParentRoot; rootSz[ver] = newSizeRoot; } bool isConnected(int ver, int x, int y) { return findRoot(ver, x) == findRoot(ver, y); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i++) { INIT_FA[i] = i; INIT_SZ[i] = 1; } // 版本 0 是初始状态 int totalVer = 0; rootFa[0] = build(1, n, INIT_FA); rootSz[0] = build(1, n, INIT_SZ); while (m--) { int opt; cin >> opt; if (opt == 1) { int a, x, y; cin >> a >> x >> y; ++totalVer; rootFa[totalVer] = rootFa[a]; rootSz[totalVer] = rootSz[a]; mergeSet(totalVer, x, y); } else if (opt == 2) { int a; cin >> a; ++totalVer; rootFa[totalVer] = rootFa[a]; rootSz[totalVer] = rootSz[a]; } else { int a, x, y; cin >> a >> x >> y; int ans = isConnected(a, x, y); cout << ans << '\n'; } } return 0; }

主程序的逻辑很简单：每次操作先根据题目要求继承某个历史版本的根，然后基于它生成新版本或者直接查询。操作 2 的“回退”实际上只是复制一个根节点下标，复杂度 O(1)，并没有复制整棵树。

6. 运行验证：如何用一组样例看懂“版本”

6.1 测试输入

使用下面的输入进行验证。

5 6 1 0 1 2 1 1 3 4 1 2 1 3 0 2 1 4 2 3 0 4 1 5

逐条操作解析：

1. 基于版本 0 合并 1 和 2，生成版本 1。
2. 基于版本 1 合并 3 和 4，生成版本 2。
3. 基于版本 2 合并 1 和 3，生成版本 3。此时 1、2、3、4 在同一个集合中，代表元素是 4。
4. 查询版本 2 中 1 和 4 是否连通。版本 2 只有“1-2”和“3-4”两个集合，1 和 4 不连通。
5. 回到版本 3，生成版本 4。
6. 查询版本 4 中 1 和 5 是否连通。版本 4 中 1 与 4 相连，5 独立，因此不连通。

6.2 预期输出

0 0

6.3 如何判断程序是否真的“可持久化”

一个简单的自检方法是：在主程序执行到第 4 步之前，手动打印rootFa[2]和rootFa[3]中节点 1 的祖先路径。

• 版本 2 中，节点 1 的父节点是 2，节点 2 的父节点是 2；
• 版本 3 中，节点 1 的父节点仍然是 2，但节点 2 的父节点已经变成 4。

也就是说，版本 2 的线段树中，2 -> 4的变化并没有污染版本 2 的结果。如果程序在查询版本 2 时输出 1，说明某个节点被错误修改了，最常见的错误是update函数修改了旧版本节点。

另一种验证方法：把输出结果去掉换行后，与手算结果逐位比对。如果第一行输出 1，优先检查mergeSet中是否使用了rootFa[a]而不是rootFa[ver]之外的其他版本根。

7. 常见问题与排查思路

如果你在评测环境遇到“段错误”，最优先检查的是MAXNODE是否足够。可持久化数据结构的空间占用是初学者最容易低估的部分。宁可一开始开大一个量级，也不要因为数组越界浪费两小时。

8. 复杂度、局限与工程建议

8.1 复杂度总结

findRoot的 O(log² n) 由两部分组成：向上跳转最多 O(log n) 次，每次通过线段树查询值需要 O(log n)。整体上，可持久化并查集比普通并查集慢一个对数级别，但在算法竞赛和大多数“回退版本”场景中，依然足够使用。

8.2 可持久化并查集的局限

普通并查集可以在 O(α(n)) 时间内完成查找，可持久化并查集做不到这一点。原因是路径压缩在可持久化中代价太高，只能依靠按秩合并维持平衡。

另外，这里返回的findRoot(ver, x)不会返回“某个版本中的根节点编号”中的全部信息。它只适合判断连通性。如果你需要查询某个集合的具体成员，需要额外维护其他数据结构，而不是直接用可持久化并查集。

还有一个容易误用的点：“回到版本”不是“撤销”。操作“回到版本 a”会生成一个新版本，这个新版本的内容等于 a，但版本总数仍然增加。它不会把当前版本“删除”，也不会影响其他旧版本的存在。

8.3 工程上的建议

在实际工程里，直接写裸数组版可持久化并查集比较少，但它背后的“可持久化数组”思想非常值得掌握。

以下几个工程建议特别实用：

• 使用内存池：用全局数组而不是vector来保存可持久化线段树节点，避免动态扩容带来的指针失效和性能抖动。
• 封装版本号概念：不要让业务代码直接操作rootFa、rootSz数组，而是封装成PersistentDSU类，提供merge(version, x, y)、same(version, x, y)、rollback(version)等方法。
• 空间估算时预留余量：可持久化结构的所有节点都保存在一个池子里，极难用完后自动回收。商业项目或长时间运行的进程，必须考虑节点淘汰策略。
• 递归深度：findRoot和query都是递归函数。在某些极端数据下，树高可能接近 log n，但递归深度不会太高；如果还是担心栈溢出，可以把递归改成显式栈或迭代版本。

这些建议不只是解决“能跑通”的问题，更是在帮你养成写可持久化结构的良好习惯：能复用的节点不要新建，能复制的根指针不要复制整棵树。

9. 总结与延伸

可持久化并查集看似被“可持久化”四个字吓住了，拆开之后其实只有三层：

第一层是并查集，负责解决“元素是否在同一个集合”的问题；第二层是可持久化数组，负责给数组加“版本”属性；第三层是把二者组装起来，用两个独立版本根分别维护fa和sz。

标题里的“一片森林，为什么只保存一个根”，最终的答案是：我们保存的“根”不是并查集森林里某棵树的根，而是可持久化线段树版本根。一个根节点就是一个版本的完整入口，里面的叶子节点装着并查集森林每一棵树根的信息。

读完这篇文章后，建议完成三个练习：

1. 手动把 6.1 节的样例跑一遍，画出每个版本的fa数组变化。
2. 把代码中的findRoot改造成显式栈的迭代写法，观察时间变化。
3. 对比“回退版本”和“批量撤销最近 k 次操作”两种需求，思考为什么前者可以直接复制根下标，后者需要额外维护历史版本栈。

如果这篇文章对你有帮助，建议收藏备用。后续可以继续关注可持久化线段树、可持久化栈、可持久化平衡树。它们底层都共享同一套“路径复制 + 版本根”的思想，一旦想明白，几个难点会一次性打通。