algorithm · 逐步优化

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

有 N 个对象，不断有人告诉你「p 和 q 现在连在一起了」(union)，你要随时回答「p 和 q 连通吗」(connected)。这就是动态连通性 (dynamic connectivity) 问题。并查集 (union-find / disjoint-set) 是它的标准解法。本页按 Sedgewick 的经典脉络，对同一个底层数组逐步优化——从 $O(N)$ 一路降到近乎 O(1)，每个 demo 都可手动执行 union / find，观察数组视图与森林视图同步变化、代码逐行点亮。四步演进：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)$ 。

同色 = 同组。 下面数组每个格子按它所属 component 染色；connected 只看两格颜色是否一致。点「下一步」按经典输入序列逐条 union，看每次合并要改写多少个格子（绿色 = 本步被改写）。

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

2 · Quick-Union：数组变森林，union 只改一根指针

core · quick-union

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

箭头指向父亲，双线圈 = root。 点「下一步」逐条 union;find 时绿色路径是「从某点走到 root」经过的边。注意观察树的高度——这正是 quick-union 的隐患所在。

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

3 · Weighted：总是小树挂大树，树高控制在 lg N 以内

balance · weighted

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

左右并排喂入同一串 union。 左边 plain quick-union（不区分大小），右边 weighted（小树挂大树，root 旁小数字 = size）。观察两边标题里的树高：同样的输入，左边越来越高，右边始终扁平。默认采用最坏输入以突出差距。

为什么是 lg N? 一个节点的深度，只在它所在的树被并进一棵更大的树时才 +1。而每次这种合并，新树规模至少是它原来的两倍（小的挂大的，大的 ≥ 小的）。规模从 1 翻到 N 最多翻 lg N 次，所以任意节点深度 $\le 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 的 weighting,m 次操作的摊还成本近乎常数——精确界是反 Ackermann 函数 $\alpha (N)$ ，现实中 $\alpha (N) \le 4$ ，基本相当于 O(1)。

从一棵高树开始。 下面预置了一棵退化的高树。选一个深处的节点点 find，观察绿色路径走到 root，随后（压缩开启时）整条路径全部挂到 root 下，树随即变扁。关闭压缩对比：树形不变，下次 find 仍需重走。

「近乎 O(1)」的含义。 单次操作最坏仍可能 $O(\log N)$ ，但对整串操作取平均（摊还分析），每次成本是 $O(\alpha (N))$ 。 $\alpha$ 是反 Ackermann 函数，增长极慢——即便 N 大到宇宙原子数量级， $\alpha (N)$ 也 $\le 4$ 。因此工程上可直接视为常数。weighting 加路径压缩，就是并查集的完整优化形态。

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

5 · 四步演进总览

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

「~1」= 摊还近乎常数 (α(N) 摊还，N 个对象 + M 次操作总成本 ≈ O(M·α(N)),α ≤ 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 最小生成树判 cycle（本仓库 MST · Kruskal 页里那段 DSU 即是其应用）、网络 / 电路连通性、变量引用等价归并、社交网络好友关系归并、图像连通域标记、离线连通查询、编译器的 union 类型等价判定等。凡是「不断合并、随时查询是否同组」的场景，大多适用。

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