并查集：连通性、路径压缩与进阶变体
并查集（Union-Find / DSU）专门解决“两个元素现在是否属于同一组，以及两组如何合并”。从朋友圈、动态连通性出发，本文逐步推导
find、union、路径压缩和按大小合并，并解释为何它能做到近似常数时间。
目录
| 章节 | 说明 |
|---|---|
| 先理解问题：不断合并的社群 | 并查集到底在维护什么 |
| 并查集这个名字是什么意思 | “并”“查”“不相交集合”分别指什么 |
| 最小接口：find 与 union | 代表元、连通性与集合数 |
| 树和 parent 数组 | 用一棵树表示一个集合 |
| 为什么朴素实现会慢 | 链状退化导致 find 为 O(n) |
| 两项关键优化 | 按大小合并与路径压缩各自解决什么 |
| 完整 Java 模板 | 可直接用于算法题的实现 |
| 复杂度：α(n) 的正确理解 | 为什么近似 O(1)，但不应写成 O(1) |
| 经典应用与边界 | 连通性、成环检测、Kruskal 与不适用场景 |
| 进阶变体 | 权重、奇偶性、离线删除与可撤销并查集 |
先理解问题：不断合并的社群
设有 6 位用户。开始时每个人各自是一个社群；之后陆续发生“建立好友关系”的事件：(0, 1)、(2, 3)、(1, 2)。此时我们希望快速回答：
- 0 和 3 是否已经在同一个社群？
- 合并 4 和 5 后，当前还剩多少个社群？
- 新边
(0, 3)会不会在无向图中形成环？
这类问题的共同点是：只合并集合，不拆分集合；而且会重复查询“是否同组”。并查集维护的不是集合内元素的顺序，而是元素之间的等价关系/连通关系。
把每个集合想成一个“朋友圈”。并查集不关心朋友圈里的聊天记录，只关心两个人最终是不是同一个朋友圈，以及两个朋友圈能否合并。
并查集这个名字是什么意思
“并查集”是 并（Union）+ 查（Find）+ 集合（Set） 的简称；英文常写作 Union-Find 或 Disjoint Set Union（DSU）。
| 名称部分 | 原文 | 含义 |
|---|---|---|
| 并 | union | 将两个已有集合合成一个集合 |
| 查 | find | 查找某个元素属于哪个集合 |
| 集 | set | 每个元素的归属集合 |
| 不相交 | disjoint | 任意两个集合没有共同元素；每个元素同一时刻只属于一个集合 |
例如初始时有三个互不重叠的集合：{0, 1}、{2, 3}、{4}。执行 union(1, 2) 后，前两个集合变成 {0, 1, 2, 3}，而 {4} 仍独立。此时 find(0) == find(3)，所以 0 和 3 属于同一集合。
这里的“查”不是遍历整个集合找元素，而是查代表元：同一集合内所有元素最终都会找到同一个代表元，因此只需比较两个代表元是否相等，就能判断是否同组。
最小接口：find 与 union
并查集的名字来自两个核心操作：
| 操作 | 语义 | 返回/效果 |
|---|---|---|
find(x) | 找到 x 所属集合的代表元（根） | 同组元素返回同一个根 |
union(a, b) | 合并 a、b 所属的两个集合 | 若原本不同组则合并成功 |
于是“是否连通”的判断自然变成：
boolean connected = find(a) == find(b);
find(x) 返回的根不是业务含义上的“老大”，只是一个稳定的集合标识；合并后谁成为根由实现策略决定。因此，不能把根 ID 当成最小元素、创建时间或负责人，除非额外维护这些信息。
树和 parent 数组
每个集合由一棵树表示，根就是代表元。parent[x] 存 x 的父节点；若 parent[x] == x，x 就是根。
例如：parent = [0, 0, 1, 3, 3] 表示 {0,1,2} 与 {3,4} 两个集合：2 指向 1，1 指向 0，最终都能走到根 0。
初始化时，每个元素独立成集：
for (int x = 0; x < n; x++) {
parent[x] = x;
size[x] = 1;
}
朴素 find 只要不断沿父指针向上走：
int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
union(a, b) 不能直接令 parent[a] = b：a、b 可能都不是根，可能把两棵树接错位置。正确步骤永远是“先找根，再接根”。
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
parent[rootB] = rootA;
}
为什么朴素实现会慢
如果总是把第二棵树接到第一棵树下，并且输入顺序不利，树会退化为链：parent[1]=2、parent[2]=3、parent[3]=4、parent[4]=5、parent[5]=5。
此时 find(1) 要走 4 条边，最坏为 O(n)。并查集真正高效的原因并不是 parent 数组本身，而是下面两项互补优化。
两项关键优化
按大小合并：先防止树长高
维护每棵树根节点的 size。合并时，让小树的根挂到大树的根下：
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
为什么这能保证 O(log n) 高度？某个节点的深度每增加 1，它所在的树至少会翻倍：只有一棵不小于它的树才能把它挂得更深。规模最多翻倍 log₂ n 次，所以树高不超过 log₂ n。
rank 是另一种等价策略：记录树高的上界，矮树挂高树；两树 rank 相等时，新根 rank 加一。实践中 size 更直观，因为它还可以直接回答集合大小。
路径压缩：查询时顺手摊平
每次 find(x) 已经走过从 x 到根的路径；回溯时让路径上的节点直接指向根，下一次查询会更短。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 回溯时改为直连根
}
return parent[x];
}
路径压缩不会改变“哪些元素属于同一个集合”，只改变到代表元的内部路径。它像整理捷径：第一次从小路走到终点后，把沿途路标都改成“直接到终点”。
为什么必须组合使用
| 策略 | 解决的问题 | 最坏/均摊效果 |
|---|---|---|
| 只按大小合并 | 不让树变成很长的链 | 树高 O(log n) |
| 只路径压缩 | 已查询路径会变短 | 初次查询仍可能走很深 |
| 两者结合 | 既限制增长，又快速摊平历史路径 | 均摊 O(α(n)) |
完整 Java 模板
下列实现使用迭代式路径压缩，避免极端输入下递归栈过深；union 的返回值非常重要：它告诉调用方这条边是否真的合并了两个集合。
public final class UnionFind {
private final int[] parent;
private final int[] size;
private int components;
public UnionFind(int n) {
if (n < 0) throw new IllegalArgumentException("n must be non-negative");
parent = new int[n];
size = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
checkIndex(x);
int root = x;
while (root != parent[root]) {
root = parent[root];
}
// 第二趟：把 x 到 root 的路径全部压平
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
public boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false;
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
components--;
return true;
}
public boolean connected(int a, int b) {
return find(a) == find(b);
}
public int componentSize(int x) {
return size[find(x)];
}
public int components() {
return components;
}
private void checkIndex(int x) {
if (x < 0 || x >= parent.length) {
throw new IndexOutOfBoundsException("invalid node: " + x);
}
}
}
常见 Bug：
- 在
union中比较 a、b，而不是find(a)、find(b)； - 成功合并后忘记
components--； size更新到子根而不是新根；- 未校验输入编号，把业务 ID 直接当作连续数组下标。
复杂度：α(n) 的正确理解
对 n 个元素执行 m 次操作，路径压缩加按秩/按大小合并的总时间是 O(m α(n))；因此单次操作的均摊时间为 O(α(n))。
α(n) 是反 Ackermann 函数。Ackermann 函数增长快得不可思议，反函数就慢得不可思议：对任何工程上可遇到的 n，α(n) 至多是一个很小的整数（通常不超过 4）。
所以可以把它当成“近似常数时间”来估算性能；但写算法分析时仍应写
O(α(n))，因为它不是严格的 O(1)，并且结论依赖于两项优化同时存在。
空间复杂度是 O(n)：parent、size 以及可选的业务元数据各保存一份每节点信息。
经典应用与边界
1. 动态连通性与环检测
无向图逐条加边 (u, v)：若 union(u, v) 返回 false，说明 u、v 原本已连通，新增边会形成环。
boolean hasCycle(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
if (!uf.union(edge[0], edge[1])) return true;
}
return false;
}
2. Kruskal 最小生成树
将边按权重从小到大处理。只有 union(u, v) 成功时，才把边加入答案；失败说明两点已在同一连通块，加入会成环。排序是主成本，因此总复杂度是 O(E log E)，并查集部分为 O(E α(V))。
flowchart LR
A["边按权重排序"] --> B["取当前最小边 u-v"]
B --> C{"find(u) == find(v)？"}
C -- 是 --> D["跳过：会成环"]
C -- 否 --> E["union(u, v)<br/>加入 MST"]
D --> F{"还有边？"}
E --> F
F -- 是 --> B
F -- 否 --> G["得到 MST"]
style E fill:#d5e8d4,stroke:#82b366
style D fill:#f8cecc,stroke:#b85450
3. 并查集不擅长什么
| 需求 | 为什么普通并查集不合适 | 更合适的工具 |
|---|---|---|
| 删除一条边后判断连通性 | DSU 只会合并，不支持拆分 | DFS/BFS、动态树或离线算法 |
| 查询两点最短路径 | 只知道是否连通，不保存路径长度 | BFS、Dijkstra |
| 有向图强连通分量 | 连通关系不是无向等价关系 | Kosaraju、Tarjan |
| 枚举集合内所有元素 | parent 树不是成员列表 | 额外维护链表/集合，或采用 small-to-large |
进阶变体
| 变体 | 在根或父边上额外维护 | 能解决的问题 |
|---|---|---|
| 集合聚合信息 | size、最小值、最大值、计数 | 查询每个连通块属性 |
| 带权并查集 | 节点到父节点的相对值 | 比例约束、差分约束 |
| 奇偶并查集 | 节点到父节点的 parity | 在线二分图检查、敌友关系 |
| 可撤销并查集 | 修改栈，不做路径压缩 | 离线动态连通性 + 分治时间线 |
关键原则是：集合级信息通常只保存在根上；节点到根的相对关系则要在 find 压缩路径时同步更新。可撤销并查集为了能够恢复旧状态，通常不能使用普通路径压缩。
练习路线
- LeetCode 547「省份数量」：先用 DFS，再用并查集，对比“静态图”和“动态加边”视角。
- LeetCode 684「冗余连接」：练习用
union的false返回值检测环。 - LeetCode 1319「连通网络的操作次数」：练习
components与冗余边计数。 - LeetCode 399「除法求值」：进入带权并查集，理解“父边相对关系”。
参考资料
- CP-Algorithms — Disjoint Set Union
- Princeton Algorithms — Union-Find
- 《算法导论》第 21 章：用于不相交集合的数据结构
- 图算法（连通分量、Kruskal 与图中的并查集应用）
- 算法复杂度分析（
O(α(n))与 Kruskal 复杂度）- 基础数据结构（数据结构选型与简版并查集说明）
评论 (0)