algorithm · 逐步优化

四步演进 · 从 quick-find 到 path compression

有 $N$ 个对象，不断有人告知「 $p$ 和 $q$ 现在连在一起了」(union)，需要随时回答「 $p$ 和 $q$ 连通吗」(connected)。这就是动态连通性 (dynamic connectivity) 问题，并查集 (union-find / disjoint-set) 是它的标准解法。本页按 Sedgewick 的经典脉络，对同一个底层数组逐步优化——从 $O(N)$ 一路降到近乎常数。四步演进依次是 Quick-Find、Quick-Union、Weighted、Path Compression。

1 · Quick-Find：直接存组号的 id 数组

naive · quick-find

最直接的设计：开一个数组 id，id[i] 存站点 $i$ 属于哪一组，用组里某个站点编号当组号。那么「 $p$ 和 $q$ 连通吗」就是一句 id[p] === id[q]——一步 $O(1)$ ，这就是 quick-find 名字的由来。问题集中在 union：要合并两组，得把整张表里所有等于 id[p] 的格子改成 id[q]，扫描一整遍 $O(N)$ 。

图 1-1 · 数组每格按所属 component 染色，同色即同组。可点「下一步」按经典序列逐条 union，绿色格是本步被改写的，数一数每次合并要动多少个。

警示 · 用它建立一遍连通关系是 $O(N^2)$ 。每条 union 都要扫描全表， $N$ 个对象做 $N-1$ 次合并就是约 $N^2$ 次数组访问；几百万个对象时这种平方级别的访问量无法承受。根因在于 id 记的是「最终归属」而非「谁连了谁」，两组合并时被并入那组的每一个成员都得改组号，没有捷径。Quick-Union 改用森林，让 union 只改一根指针。

2 · Quick-Union：把数组读成森林

core · quick-union

换个记法：parent[i] 不再存最终组号，只存「我的父亲是谁」。顺着 parent 一路往上走，走到指向自己的那个节点就是 root——它是这棵树（这一组）的代表。于是同一个数组现在是一片森林。union(p, q) 只要找到两边的 root，把一棵的 root 挂到另一棵 root 下，只改一个指针，再不用扫全表。

图 2-1 · 箭头指向父亲，双线圈是 root；find 时绿色路径是从某点走到 root 经过的边。可逐条 union，留意树的高度怎么长。

警示 · 树可能退化成一条长链。切到「最坏输入」可以看到：每次都把整棵旧树挂到新点下，树高逐步逼近 $N$ 。这时 find 要从叶子一路走到顶，union 与 connected 都退化成 $O(N)$ ，不再优于 quick-find。问题出在合并时不分大小，没有控制挂接之后树会不会变高。Weighted 用一个 size 数组始终让小树挂到大树下，把树高压到 $\lg N$ 以内。

3 · Weighted：小树挂大树

balance · weighted

quick-union 会退化，是因为合并时不区分大小，可能把高树接到了矮树下。解决方法相当简单：额外用一个 size 数组记下每棵树有多少节点，合并时始终把小树挂到大树的 root 下。这样每个节点的深度，只有在它所在的树规模翻倍时才会加一，而规模最多翻倍 $\lg N$ 次，所以树高不超过 $\lg N$ ，union 与 find 都是 $O(\log N)$ 。

图 3-1 · 左右并排喂入同一串 union：左边不区分大小，右边小树挂大树（root 旁的小数字是 size）。默认用最坏输入，可对比两边标题里的树高。

建议 · 树高界的来由值得单独想一遍：一个节点的深度，只在它所在的树被并进一棵更大的树时才加一；而每次这种合并，新树规模至少是它原来的两倍（小的挂大的，大的不小于小的）。规模从 1 翻到 $N$ 最多翻 $\lg N$ 次，所以任意节点深度不超过 $\lg N$ 。一千万个对象，树高约为 23。 $O(\log N)$ 已经相当好，但每次 find 仍需从某点走 $\lg N$ 步到 root——Path Compression 顺路把经过的节点全部改挂到 root。

4 · Path Compression：find 一趟压平路径

advanced · path compression

最后一项优化几乎不增加成本：find(x) 本来就要从 $x$ 一路走到 root，在这一次遍历中，可以把沿途经过的每个节点都直接改挂到 root 下。这趟只多花常数代价，却让这条路径上所有点的下次 find 都一步到位。配合 Weighted 的加权合并， $m$ 次操作的摊还成本近乎常数——精确界是反 Ackermann 函数 $\alpha(N)$ ，现实中 $\alpha(N) \le 4$ 。

图 4-1 · 预置一棵退化的高树。可选深处的节点点 find，看绿色路径走到 root 后整条路径被挂到 root 下；关掉压缩则树形不变，下次 find 仍需重走。

建议 ·「近乎常数」要按摊还口径读。单次操作最坏仍可能 $O(\log N)$ ，但对整串操作取平均，每次成本是 $O(\alpha(N))$ 。 $\alpha$ 是反 Ackermann 函数，增长极慢——即便 $N$ 大到宇宙原子数量级， $\alpha(N)$ 也不超过 4，因此工程上可直接视为常数。加权合并配路径压缩，就是并查集的完整优化形态。

另有一种变体叫路径折半 (path halving)：不想走两趟时，可在一趟里把每个节点直接指向它的祖父节点（parent[x] = parent[parent[x]]; x = parent[x];），路径也会逐步减半。效果与两趟压缩同阶，代码更短，是许多工业实现采用的版本。

5 · 四步演进总览

同一个「 $N$ 个对象加 union / connected」的问题，底层数组始终不变，变的是如何解读它、合并时挂在哪边、查询时是否顺带整理。

表 5-1 · 四步的成本对照。「~1」指摊还近乎常数：N 个对象加 M 次操作的总成本约 $O(M \cdot \alpha(N))$ ，而 $\alpha \le 4$ 。
实现	初始化	union	connected / find	关键 trick
quick-find	N	N	1	id 数组直接存组号
quick-union	N	树高	树高（最坏 N）	parent 数组构成森林
weighted QU	N	lg N	lg N	小树挂大树
weighted + 压缩	N	~1	~1	find 时压平路径

它的落地场景相当广：Kruskal 最小生成树判环（MST · Kruskal 里那段 DSU 即是其应用）、网络与电路连通性、变量引用等价归并、社交网络好友关系归并、图像连通域标记、离线连通查询、编译器的 union 类型等价判定。凡是「不断合并、随时查询是否同组」的场景，大多适用。

并查集的森林是「只向上指 parent、不维护孩子」的极简树，与最小生成树的 Kruskal 紧密配合；它的近乎常数摊还依赖于把一次昂贵操作的收益分摊给后续操作，这种摊还视角与区间查询里各种预处理结构思路相通。