第08章 不相交集类：Union-Find 与等价关系

这一篇在干嘛？

动态等价问题：一堆元素，反复问”a 和 b 在同一个集合里吗？“以及”把 a、b 所在的集合合并”。并查集（Union-Find/不相交集森林）用少到离谱的代码把两个操作都做到近乎 $O(1)$（摊还 $O(\alpha (N))$，$\alpha$ 是反阿克曼函数，实战中 ≤ 4）。它是 Kruskal 最小生成树、迷宫生成、连通分量判定的核心零件。

8.1 等价关系

集合 $S$ 上的关系 $\sim$ 是等价关系，当且仅当满足三条：

• 自反：$a\sim a$
• 对称：$a\sim b\Rightarrow b\sim a$
• 传递：$a\sim b,b\sim c\Rightarrow a\sim c$

$\ge$ 是自反+传递但不对称；相等 = 是完美等价关系。等价关系把集合切成互不相交的等价类——动态等价问题的目标就是在线维护这些类。

8.2 两个操作

• find(x)：返回 x 所在等价类的代表（类内所有元素返回同一个名字，类间不同）。
• union(x, y)：把 x 和 y 所在的两个类合并成一个。

注意算法的”感受不到名字”特性：find(a) == find(b) 判等价，但具体代表是谁无所谓——只要同一类内一致。

8.3 基础结构：森林 + 父指针数组

每个集合是一棵树；s[i] 存节点 i 的父亲下标，根的父亲存自己（或特殊标记）：

// find：一路向上找根
int find(int x) {
    while (s[x] >= 0)     // 根的值是负的（可兼存集合大小）
        x = s[x];
    return x;
}
 
// 朴素 union：把一棵树挂到另一棵下面
void unionSets(int root1, int root2) {
    s[root2] = root1;
}

朴素 union 的隐患：乱挂会长出一条链，find 退化 $O(N)$——最坏树就是逐个挂形成的链（N=16 时深度可达 15）。

8.4 聪明合并：按大小 / 按高度

union-by-size：小树挂到大树下。根数组存负的集合大小：s[root1] += s[root2]; s[root2] = root1;

union-by-height（rank）：矮树挂到高树下。只有两树等高时高度才 +1——树高增长慢得多。可证：连续 M 次 union/find 总代价 $O(M\log N)$（树的深度 ≤ $\lfloor \log N\rfloor$，因为深度 d 的节点至少有 $2^d$ 个后代）。

白话：合并像公司并购——小公司并入大公司（按大小），或矮楼并入高楼（按高度），都防止”细长烟囱”出现。一个数组就够：根位置存负数，负数大小 = 集合大小，一举两得。

8.5 路径压缩：find 顺手修路

find 返回途中，把路径上每个节点直接改挂到根：

int find(int x) {
    if (s[x] < 0)          // 根
        return x;
    return s[x] = find(s[x]);   // 递归找根，顺手把父亲改成根（路径压缩）
}

白话：走过一遍的路全部修成高速公路——第一次 find 可能很深，之后这条线上的任何人查根都是一步直达。路径压缩会改变树高，让”按高度”失效（但”按大小”依然可靠），所以标准搭配是 union-by-rank（近似高度）+ 路径压缩。

8.6 终极复杂度：O(α(N))

Tarjan 的著名结果：union-by-rank + 路径压缩，M 次操作总代价 $O(M\cdot \alpha (N))$。$\alpha (N)$ 是反阿克曼函数——增长慢到荒谬：$N=2^{65536}$ 时 $\alpha (N)\le 4$。

它是 Ω 下界匹配的：单次操作虽非严格 $O(1)$，但任何由 union 和 find 组成的操作序列都不可能更快了。另外注意一个微妙结论：路径压缩单独使用（不做按秩合并）最坏是 $\Theta (M\log N)$——两个技巧要绑定才有 $\alpha$ 界。

M 遍 vs M·log·log·… 的直觉（书中 Lemma 8.x 的递归分解）: 把节点按”秩区间”分层分析压缩的收益，每层贡献一个 ${\log }^{\ast }N$ 级别的因子，最终折叠成 $\alpha (N)$。这是全书理论最深的证明之一，初学记住结论即可。

8.7 应用：迷宫生成与连通性

迷宫生成（50×88 格示例）：每个格子是一个节点，与相邻格子的”墙”是待选边。不断随机选墙，若两侧格子不连通（find 不同）就拆墙 union；连通块从 $N$ 个降到 1 个时迷宫完成。

第 9 章 Kruskal 算法判定”这条边会不会成环”用的正是同一招：边的两端 find 相同 → 成环，跳过。

常见坑

① 只做路径压缩不做按秩：最坏 $\Theta (M\log N)$，”$\alpha$ 界”需要两者配合。② find 用循环实现忘了先存路径：回写父亲时要沿原路径走一遍，递归版 s[x]=find(s[x]) 一行搞定最不易错。③ 把 find 的返回值当”类名”持久化：后续 union 会改变代表元，判等价要当场比较两次 find。

通关标准

学完本篇你应该能做到：① 默写 union-by-size 与路径压缩 find 的代码（各约 5 行）；② 解释为什么按秩+压缩能到 $O(\alpha (N))$、以及为什么单用压缩不行；③ 用并查集判定无向图加边是否成环；④ 用并查集描述迷宫生成流程。

为什么根节点的数组值存"负的大小"很划算？

一个数组两用：非根存父亲下标，根存集合大小（负号当”我是根”的标记）。union-by-size 判断和更新都不需要第二块内存。

路径压缩为什么不会破坏 find 的正确性？

压缩只改父亲指针、不改集合归属：被提直的节点与根本来就在同一集合。它把树变浅，find 语义（返回根）不变。

α(N) 大致是多大？为什么可以说"近乎常数"？

反阿克曼函数。N 取宇宙级原子数（$2^{65536}$）时 α(N) ≤ 4。任何现实规模下 M·α(N) 与 M 几乎无差别。

迷宫生成中"选墙拆墙"如何用并查集判定？

每格初始化为独立集合。随机选墙，两侧格子 find 不同 → 拆墙（union），否则跳过（拆了会成环，迷宫出现环路就不再是完美迷宫）。集合数从 N 减到 1 时结束。

union-by-height 在路径压缩下为什么失效？

压缩把路径节点直挂根，树高下降但存储的高度值没更新（更新需要额外遍历），高度信息从此不准。按大小不受影响（元素个数不变），所以实战用 rank（记录的”高度上界”）+ 压缩。