一、问题定义
不相交集数据结构（Disjoint Set Union，DSU），通常称为并查集（Union-Find），维护一组互不相交的动态集合 $S = {S_1, S_2, \ldots, S_k}$。每个集合有一个代表元（representative），通常是集合中的某个特定成员。
核心操作：
MAKE-SET(x)：创建仅包含元素 $x$ 的新集合。$x$ 是代表元。UNION(x, y)：将包含 $x$ 和 $y$ 的两个集合合并为一个集合，选择新代表元。FIND(x)：返回包含 $x$ 的集合的代表元。
关键约束：$x$ 和 $y$ 始终属于唯一的一个集合。UNION 后原来的两个集合不再存在。
应用场景极广：
- Kruskal 的最小生成树算法
- 图像处理中的连通分量标记
- 网络连接性判断
- 等价类划分
- 渗透问题（Percolation）
- 游戏中的朋友圈/公会合并
二、四种实现演进
2.1 Quick-Find — 优化 Find
数据结构：数组 id[]，id[x] 表示 $x$ 所属集合的代表元。同一个集合的所有元素具有相同的 id。
class QuickFind {
private int[] id;
public QuickFind(int n) {
id = new int[n];
for (int i = 0; i < n; i++) id[i] = i;
}
public int find(int x) {
return id[x];
}
public void union(int x, int y) {
int idX = id[x], idY = id[y];
if (idX == idY) return;
for (int i = 0; i < id.length; i++) {
if (id[i] == idX) id[i] = idY;
}
}
public boolean connected(int x, int y) {
return id[x] == id[y];
}
}
|
分析：find 很快（$O(1)$），但 union 太慢（$O(n)$）。$n$ 个元素的 $n-1$ 次 union 需要 $O(n^2)$ 时间。
2.2 Quick-Union — 优化 Union
数据结构：使用树结构（森林）。parent[x] 指向 $x$ 的父节点，根节点指向自身。每个集合是一棵树，根是代表元。
class QuickUnion {
private int[] parent;
public QuickUnion(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
while (x != parent[x]) {
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
|
分析：union 只需 $O(h)$（$h$ 是树的高度），但最坏情况下树退化为链（$h = n$），每次 find 和 union 都是 $O(n)$。
问题根源：union 总是将第一棵树的根作为第二棵树根的子节点，不控制树的生长方向，导致树可能变得非常高。
2.3 Weighted Union（按大小/秩合并）
改进：始终将较小的树合并到较大的树下。维护 size[x]（或 rank[x]）记录子树大小。
class WeightedUnion {
private int[] parent;
private int[] size;
public WeightedUnion(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
while (x != parent[x]) {
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (size[rx] < size[ry]) {
parent[rx] = ry;
size[ry] += size[rx];
} else {
parent[ry] = rx;
size[rx] += size[ry];
}
}
}
|
定理：使用按大小合并后，任意树的高度 $\leq \lfloor \log_2 n \rfloor$。
证明：树的高度增加 1 当且仅当两棵高度相等的树合并（较小的树合并到较大的树时，大树的根不变，高度不变）。通过归纳：大小为 $s$ 的树的高度最多为 $\lfloor \log_2 s \rfloor$（因为每次高度增加意味着树的大小至少翻倍）。$\square$
因此 find 和 union 都降为 $O(\log n)$。
2.4 路径压缩（Path Compression）+ 按秩合并 — 接近 O(1)
路径压缩：在 find(x) 的过程中，将路径上所有节点的父指针直接指向根。这摊平了后续查找的成本。
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public int findIterative(int x) {
int root = x;
while (root != parent[root]) {
root = parent[root];
}
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
public boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank[rx] < rank[ry]) {
parent[rx] = ry;
} else if (rank[rx] > rank[ry]) {
parent[ry] = rx;
} else {
parent[ry] = rx;
rank[rx]++;
}
return true;
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
|
三、复杂度分析 — $O(\alpha(n))$ 的奇迹
3.1 反 Ackermann 函数
带有路径压缩和按秩合并的并查集，其 find 和 union 操作的摊还复杂度为 $O(\alpha(n))$，其中 $\alpha(n)$ 是反 Ackermann 函数。
对于任何可实践的 $n$（$n \leq 2^{65536}$），$\alpha(n) \leq 5$。即在实际应用中，每个操作可视为几乎 $O(1)$。
Ackermann 函数（增长极快）：
$$A(0, m) = m+1$$
$$A(k+1, 0) = A(k, 1)$$
$$A(k+1, m+1) = A(k, A(k+1, m))$$
$A(1, n) = 2+(n+3)-3 = n+2$（线性）
$A(2, n) = 2n+3$（线性）
$A(3, n) = 2^{n+3}-3$（指数级）
$A(4, n) = 2^{2^{2^{\cdots^2}}} - 3$（塔式指数，高度 $n+3$）
$A(4, 4) \approx 2^{2^{2^{2^{2^{2^{2}}}}}}$ — 远超宇宙中的原子数
反 Ackermann 函数：$\alpha(n) = \min{k \mid A(k, 1) \geq n}$。增长极其缓慢。
3.2 $O(\alpha(n))$ 推导直觉
虽然严格证明非常繁复（Tarjan 1975），但直觉如下：
- 按秩合并确保秩为 $r$ 的节点的子树至少有 $2^r$ 个节点（通过归纳：两个秩为 $r$ 的树合并才产生秩为 $r+1$ 的树，至少 $2^r + 2^r = 2^{r+1}$ 个节点）
- 路径压缩为节点”付费”——每次
find 遍历路径，将路径上（大多数）节点直接连到根，后续访问这些节点的成本大幅降低
- 将秩分为若干”组”（以 Ackermann 函数的反函数为界），可证明在任意操作序列中，高级秩组的节点的父指针修改次数受到严格限制
结论：总代价正比于 $n \cdot \alpha(n)$，其中 $\alpha(n)$ 对任何实际输入都可视为常数。
四、完整 Java 实现（生产级）
class DisjointSetUnion {
private final int[] parent;
private final int[] rank;
private int components;
public DisjointSetUnion(int n) {
parent = new int[n];
rank = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank[rx] < rank[ry]) {
parent[rx] = ry;
} else if (rank[rx] > rank[ry]) {
parent[ry] = rx;
} else {
parent[ry] = rx;
rank[rx]++;
}
components--;
return true;
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public int getComponents() {
return components;
}
public Map<Integer, Integer> getComponentSizes() {
Map<Integer, Integer> sizes = new HashMap<>();
for (int i = 0; i < parent.length; i++) {
int root = find(i);
sizes.put(root, sizes.getOrDefault(root, 0) + 1);
}
return sizes;
}
}
|
五、经典应用
5.1 Kruskal 最小生成树
并查集是 Kruskal 算法的核心数据结构——用于高效检测加入某条边是否会形成环：
List<Edge> kruskalMST(List<Edge> edges, int n) {
Collections.sort(edges);
DisjointSetUnion dsu = new DisjointSetUnion(n);
List<Edge> mst = new ArrayList<>();
for (Edge e : edges) {
if (dsu.union(e.u, e.v)) {
mst.add(e);
if (mst.size() == n - 1) break;
}
}
return mst;
}
|
5.2 连通分量标记（Connected Components Labeling）
在图像处理中，需要标记二值图像中的连通区域。可以用并查集做两趟扫描：
int[] labelComponents(int[][] image, int rows, int cols) {
DisjointSetUnion dsu = new DisjointSetUnion(rows * cols);
int[] parent = new int[rows * cols];
Arrays.fill(parent, -1);
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (image[r][c] == 0) continue;
int idx = r * cols + c;
parent[idx] = idx;
if (r > 0 && image[r-1][c] == 1) dsu.union(idx, (r-1)*cols + c);
if (c > 0 && image[r][c-1] == 1) dsu.union(idx, r*cols + (c-1));
}
}
Map<Integer, Integer> labelMap = new HashMap<>();
int nextLabel = 1;
int[] labels = new int[rows * cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int idx = r * cols + c;
if (parent[idx] != -1) {
int root = dsu.find(idx);
labels[idx] = labelMap.computeIfAbsent(root, k -> nextLabel++);
}
}
}
return labels;
}
|
5.3 渗透问题（Percolation）
给定 $n \times n$ 的网格，每个 cell 以概率 $p$ 开放。判断是否存在从顶部到底部的连通路径。使用并查集（带虚拟顶层和底层节点），每次开放一个新 cell 时将其与已开放的相邻 cell union。检查虚拟顶层和虚拟底层是否连通即可判断渗透。
5.4 等价关系处理
给定形如 a == b 和 a != b 的约束，判断是否所有约束可同时满足。策略：先用并查集处理所有 == 约束（union(a, b)），再检查所有 != 约束（若 find(a) == find(b) 则矛盾）。
boolean satisfiable(int n, int[][] equations) {
DisjointSetUnion dsu = new DisjointSetUnion(26);
for (int[] eq : equations) {
if (eq[1] == '=') dsu.union(eq[0] - 'a', eq[3] - 'a');
}
for (int[] eq : equations) {
if (eq[1] == '!' && dsu.connected(eq[0] - 'a', eq[3] - 'a')) {
return false;
}
}
return true;
}
|
六、并查集的变体与扩展
6.1 带权并查集（Weighted DSU）
除了维护集合关系，还在边上维护”权值”。例如在食物链问题中，dist[x] 表示 $x$ 与父节点之间的关系类型（0: 同类, 1: 吃, 2: 被吃）：
class WeightedDSU {
int[] parent, rank;
int[] dist;
int find(int x) {
if (parent[x] != x) {
int p = parent[x];
parent[x] = find(parent[x]);
dist[x] = (dist[x] + dist[p]) % 3;
}
return parent[x];
}
boolean union(int x, int y, int relation) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return (dist[x] - dist[y] + 3) % 3 == relation;
}
parent[rx] = ry;
dist[rx] = (dist[y] - dist[x] + relation + 3) % 3;
return true;
}
}
|
6.2 可撤销并查集（Rollback DSU）
支持 undo 操作的并查集。需要改为按秩合并（不能用路径压缩），用栈记录每次 union 的修改。常用于离线算法（如分治、线段树分治）。
6.3 持久化并查集（Persistent DSU）
使用持久化数组（如基于平衡树或线段树实现），可以在 $O(\log n)$ 时间内访问历史版本的并查集状态。
七、面试常见追问
问题一：为什么路径压缩 + 按秩合并的复杂度接近但非严格 $O(1)$？
回答：虽然对任何现实输入 $\alpha(n) \leq 5$ 与常数无异，但从渐近分析角度，$\alpha(n)$ 随 $n$ 趋于无穷而发散（尽管极其缓慢）。Tarjan 在 1975 年严格证明下界为 $\Omega(\alpha(n))$，因此不可能达到 $O(1)$。
问题二：路径压缩中使用递归写法会不会导致栈溢出？
回答：在最坏情况下（链状结构），递归深度可以达到 $n$。对于 $n > 10^4$ 的场景，使用迭代版 find（两趟法）是更安全的选择。或者将递归改为尾递归 + 编译器优化（但 Java 目前不支持尾递归优化）。
问题三：按秩合并 vs 按大小合并，哪个更好？
回答：二者等效（Tarjan 证明二者与路径压缩组合后都是 $O(\alpha(n))$）。按秩合并的常数略小（不用维护 $size$ 的加法），但差别微乎其微。实践中按大小合并更直观——“把小的挂到大的下面”。
问题四：什么时候不应该使用路径压缩？
回答：当需要支持 undo 操作或需要知道树的具体结构时，路径压缩破坏了树的结构信息。此时只用按秩合并（$O(\log n)$ 每操作），但保留了父子关系用于回滚。
问题五：并查集能否处理”删除边”的操作？
回答：标准并查集不支持删除（它只知道合并）。如果需要支持边删除+在线查询连通性，需要更强大的数据结构（如 Link-Cut Tree 或 Euler Tour Tree）。或者离线处理（从后往前，将删除变为添加）。
八、总结
并查集（Disjoint Set Union）以其极致的简洁性和几乎常数级的复杂度，成为算法设计中不可或缺的工具：
算法演进：
QuickFind → find O(1), union O(n)
QuickUnion → union O(h), find O(h) （树可退化为链，h=n）
Weighted → O(log n) 保证（按大小合并）
+ 路径压缩 → O(α(n)) ≈ O(1) （Tarjan 1975）
|
核心设计思想：
- 按秩/大小合并：防止树退化为链
- 路径压缩：所有触及的节点直接受益，后续更快
- 摊还分析：$\alpha(n)$ 的反 Ackermann 分析是算法分析历史上的经典篇章
并查集的应用远超图算法范畴——它是处理等价关系和动态连通性的通用工具。下一篇【数据结构与算法体系】van-Emde-Boas-树 将带你进入另一种极致：当 key 的取值范围有限时，优先队列操作可以达到 $O(\log \log n)$。
