企业官网建设流程全解析

直接用数组记录每个元素所在的集合编号，是最朴素的想法。初始化时belong[i] = i，Union(a, b)就先扫描一遍数组把所有属于 b 的元素改成 a，时间复杂度 O(n)。如果连续做 m 次 Union，总代价就是 O(mn)，n 稍微大一点（比如 10 万）就完全没法用。

于是就有了树形表示法：每个集合是一棵树，根节点作为集合的“代表元素”。parent 数组里，根节点指向自己，其余节点指向它的父节点。这样 Find(x) 只需要沿着 parent 往上走到根；Union(a, b) 则是把 a 所在树的根接到 b 所在树的根下面。问题看似简单，但 Union 的写法从粗糙到成熟，我实际经历了三次比较关键的改进，每一步都是在特定问题场景下逼出来的。这篇文章就按时间线把这三次改进完整拆开讲一遍，也把每一步背后的复杂度分析、边界条件说清楚。

1. 等价类与并查集问题的本质

1.1 等价关系的数学背景

先明确一下“等价类”这个概念。离散数学里，一个定义在集合 S 上的关系 R，如果同时满足自反性、对称性、传递性，就称为等价关系。

举个例子：无向图里“两个顶点之间有一条路径”就是一种等价关系。任何顶点和它自己当然是连通的（自反）；a 和 b 连通，则 b 和 a 也连通（对称）；a 和 b 连通，b 和 c 连通，则 a 和 c 连通（传递）。这个等价关系会把顶点集划分成若干个连通分量，每个连通分量就是一个等价类。

等价关系的一个关键性质就是：它能把集合划分成互不相交的等价类，所有等价类的并集就是原来的全集。这个“划分”的性质，正好对应网络上常见的“圈子”：一个社交平台上的用户，互为好友关系形成的闭包可以看作等价关系，每个“朋友圈”就是一个等价类。

计算机里维护等价类，核心就两个操作：

• Find(x)：查询元素 x 属于哪个等价类（通常返回集合的“代表元素”）。
• Union(a, b)：把 a 和 b 所在的两个等价类合并成一个。

这个数据结构就是并查集（Union-Find Set）。它的难点在于：合并操作会改变集合的归属关系，而查询操作又必须实时反映这种变化。要让这两个操作都足够快，就需要一套精巧的表示方法。

1.2 从数组表示到森林表示

最直接的表示方法是数组：belong[x]表示元素 x 所属的集合编号。查询是 O(1) 的，但合并需要扫描全数组，代价太高。

于是改用森林。森林里每棵树代表一个集合，树的根节点是集合的代表元素。parent 数组记录每个节点的父节点，根节点的父节点指向自己。这样：

• Find(x)不断往上找父节点，直到parent[x] == x。
• Union(a, b)找到 a 和 b 的根，把其中一个根接到另一个根下面。

森林表示的核心优点在于：合并只需要移动一个根节点，不需要扫描大量元素。Union 的开销从 O(n) 降到了 O(树高)，Find 也是 O(树高)。这看起来已经很理想了，但“树高”这个变量恰恰是最大的隐患——如果合并方向控制不好，树会越来越“歪”，性能会急剧退化。接下来进入正题，看看 Union 函数的每一次演进。

2. 朴素版本的 Union：正确性就站不住

2.1 最直白的写法

第一次写并查集的时候，最容易写出这样的版本：

#define MAXN 100005 int parent[MAXN]; // 初始化：每个元素独立成集合 void Init(int n) { for (int i = 0; i < n; i++) { parent[i] = i; } } // 朴素查找：一路向上找根 int Find(int x) { while (parent[x] != x) { x = parent[x]; } return x; } // 朴素合并：直接把 a 挂在 b 下面 void Union(int a, int b) { parent[a] = b; }

当时我是怎么想的呢？既然 parent[a] 表示 a 的父节点，那把 a 的父节点设成 b，不就等于把 a 所在集合合并到 b 所在集合了吗？

这个逻辑在“a 和 b 恰好都是各自集合的根”时勉强成立。但一旦 a 或者 b 不是根节点，问题就来了。

2.2 两个致命的逻辑漏洞

先看一个场景：集合 A = {1, 2, 3}，树长这样：1 → 2 → 3，3 是根。集合 B = {4, 5}，4 → 5，5 是根。现在执行Union(2, 5)，希望把两个集合合并。

按上面的朴素写法，执行parent[2] = 5，结果是：1 → 2 → 5 → 4，集合 A 里的元素 3 呢？3 依然是根（parent[3] = 3），它跟整棵树完全断了联系！原本在集合 A 里的 3 被“悬空”了。正确结果应该是合并后所有元素都在一棵树里，现在 3 变成了孤岛。

这就是第一个致命问题：合并前没有把参与操作的节点提到根，导致部分元素丢失。正确做法是必须先Find(a)、Find(b)拿到两个真正的根，再修改根的指向。注意这里不是简单的“效率低”，而是逻辑直接错误。

第二个问题藏得更深：即使 a 和 b 恰好是根，直接修改 parent 也不顾树的高度，会导致树严重退化。

看这组操作序列：

Union(1, 2) // parent[1] = 2，树高 2：1→2 Union(2, 3) // parent[2] = 3，树高 3：1→2→3 Union(3, 4) // parent[3] = 4，树高 4：1→2→3→4 ... Union(n-1, n) // 树高 n：1→2→...→n

连续 n 次 Union 之后，形成一条长度为 n 的链表。此时Find(1)要沿着链条走 n 步，时间复杂度 O(n)。如果 m 次操作全是这种 Find，总复杂度 O(mn)，等于白优化回去了。

这里可以用一张表直观感受退化趋势：

所以，问题从“怎么把逻辑写对”，迅速变成了“怎么写才能保证树高不会失控”。这就引出了第一次改进。

3. 第一次改进：先找根再合并，修正逻辑漏洞

3.1 标准 Union 的雏形

第一次改进的核心改动很小：在修改 parent 之前，先分别求出 a 和 b 的根，只对根操作。

void Union(int a, int b) { int ra = Find(a); int rb = Find(b); if (ra == rb) { // 已经在一个集合里，什么都不做 return; } parent[ra] = rb; // 把 ra 挂到 rb 下面 }

这次改进至少保证了正确性：union 操作永远不会丢元素。因为 ra 和 rb 都是根节点，把其中一个根挂到另一个根下面，整棵树只是改变了根的父节点，所有子树都还连着，没有节点被孤立。

另外还要做一件很重要的补充：如果两个元素已经在同一个集合里，直接返回。少了这个判断，可能会出现把根挂到自己身上的情况，虽然不影响正确性，但会在某些实现里产生额外的无效操作。

3.2 复杂度隐患依然存在

但说实话，这个版本的复杂度并没有质的改善。最坏情况下，树依然会退化成链表。

举个例子，如果操作序列是：

Union(2, 1) // parent[2] = 1 Union(3, 2) // 先Find(3)=3, Find(2)=1，然后 parent[3]=1，树高 2 Union(4, 3) // parent[4]=1，树高 2

这种先 Find 再合并的写法，把新节点往根上挂，树反而比较矮。但换一个顺序试试：

Union(1, 2) // parent[1]=2，树高 2 Union(2, 3) // parent[2]=3，树高 3 Union(3, 4) // parent[3]=4，树高 4 ...

每一次都是把当前树的根挂到新节点下面，树长成了一条链。为什么？因为Union(2, 3)里，Find(2) 返回的是 2（此时 2 还不是根吗？前面 parent[1]=2，所以 2 确实是根），Find(3)=3，然后 parent[2]=3，等于把整棵树往右挪了一格。重复下去，自然形成链。

效率层面：m 次 Union-Find 操作，最坏 O(mn)。n 取 10 万、m 取 10 万时，操作量约 10^10 次，超时是必然的。

当时我实测过一个案例：n = 100000，执行上面那种“链式 Union”，再连续 Find 尾部节点，程序跑了接近 2 秒。这在比赛或者大规模数据场景里是不可接受的。于是有了第二次改进。

4. 第二次改进：按大小合并，让树保持平衡

4.1 加一个 size 数组，让小树挂大树下面

解决退化成链的方法很直观：别管谁先谁后，永远把“小树”挂到“大树”下面。这里的“大小”指的是集合的元素个数，不是树高。实现上多维护一个 size 数组。

int parent[MAXN]; int size[MAXN]; void Init(int n) { for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } void Union(int a, int b) { int ra = Find(a); int rb = Find(b); if (ra == rb) { return; } // 始终把元素少的树挂到元素多的树上 if (size[ra] < size[rb]) { parent[ra] = rb; size[rb] += size[ra]; } else { parent[rb] = ra; size[ra] += size[rb]; } }

这里有个容易写反的点：parent[ra] = rb意味着把 ra 集合整棵挂到 rb 上，那么合并后的集合大小应该是size[rb] += size[ra]，千万别写成size[ra] += size[rb]或者忘记更新。我当时就犯过这个错：合并操作后，size 数组的值不对，导致后续判断方向和实际树的大小不匹配，整个平衡策略就失效了。

4.2 为什么树高被限制在 O(log n)

这个策略的牛之处在于：它保证每个节点向上走到根的路径长度不会超过 log₂n。关键观察是：一个节点的深度每增加 1，它所在的集合大小至少翻倍。

为什么？因为只有当节点所在的小树被挂到另一棵大树下面时，这个节点的深度才会加 1。假设节点原来所在集合大小为 s，被挂到集合大小至少为 s 的树上（因为只把小树挂大树，所以另一棵树的大小 ≥ s），合并后这个节点所在集合大小变成 s + 另一棵树大小 ≥ 2s。

深度加 1，集合大小翻倍；深度加 2，集合大小翻 4 倍……一个节点深度为 d 时，它所在集合大小至少是 2^d。集合大小最大是 n，所以 2^d ≤ n，d ≤ log₂n。

这样，Find 操作从最坏 O(n) 变成了 O(log n)。m 次操作的总复杂度是 O(m log n)，这已经是一个非常大的进步了。

4.3 还有必要继续改进吗

从算法复杂度的角度看，O(m log n) 已经可以应对大多数编程题的规模了：n = 10^5，m = 10^5，log n ≈ 17，总操作量约 170 万，轻松跑完。哪怕 n = 10^6，log n ≈ 20，也不成问题。

但在一些极端场景下——查询操作特别多、或者 n 达到 10^7 以上——log n 这个因子依然会拖后腿。更重要的是，在按大小合并的保证下我们还能看得更远：如果能想办法让树变得更“扁”，Find 的次数就会更少。带着这个想法，我开始了第三次改进。

5. 第三次改进：路径压缩，让树彻底变扁

5.1 思想：把找过的路直接“压平”

按大小合并的策略是从合并的方向上控制树高。但还有一个潜在的优化空间：Find 操作本身。

假设有一次 Find(x) 从 x 一路向上走了 h 步到根。这个过程中经过的每个节点，它们的根其实都是同一个。那为什么不顺便把这些节点的父指针直接指向根？下次再 Find 这些节点时，一步就到根了。这个顺手做的事，就叫路径压缩。

这就像你第一次去一个新办公楼找某层，需要一层层问路；问完之后，你直接把沿途认识的人都拉进一个群里，并且告诉他们“楼层管理员是某某，要找他就直接联系”，以后谁再问路，不用再一层层爬楼了。

路径压缩的代码非常短，递归版尤其简洁：

int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); // 递归，把 x 直接挂到根下面 } return parent[x]; }

这个版本在递归返回时会把路径上所有节点的 parent 直接指向根。如果担心递归深度的问题，可以改成迭代版：

int Find(int x) { int root = x; while (parent[root] != root) { root = parent[root]; } // 第二次循环，把路径上的节点全部指向 root while (x != root) { int next = parent[x]; parent[x] = root; x = next; } return root; }

迭代版做了两趟：第一趟找根，第二趟修改路径上所有节点的父指针。第一趟找完根之后，第二趟还是会走一遍原来的路径，复杂度是 O(路径长度)。不过这个路径长度在路径压缩的帮助下会迅速缩短，实际开销很小。

5.2 与按大小合并结合，形成最终版

第三次改进的关键，并不是单独把路径压缩塞进 Find 里，而是把路径压缩和按大小合并组合在一起用。很多教程里只强调路径压缩，忽略了按大小合并，这是不对的。只做路径压缩、不做按大小合并，最坏情况下的复杂度依然可能是 O(m log n)；如果同时做，复杂度才能保证近似常数。下面的完整版是实践中比较推荐的写法：

int parent[MAXN]; int sz[MAXN]; void Init(int n) { for (int i = 0; i < n; i++) { parent[i] = i; sz[i] = 1; } } int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); } return parent[x]; } void Union(int a, int b) { int ra = Find(a); int rb = Find(b); if (ra == rb) { return; } if (sz[ra] < sz[rb]) { parent[ra] = rb; sz[rb] += sz[ra]; } else { parent[rb] = ra; sz[ra] += sz[rb]; } }

对于偶尔需要自己造轮子或者刷题的人来说，这个版本已经足够。认真体会一下：sz数组保证了合并后树高不会失去控制，Find又通过路径压缩把已经访问过的节点直接挂到根。经过一次 Find 的树会变得非常扁平，后续操作都是“走一两步就到根”。

5.3 复杂度：从 log 到反阿克曼函数

加了路径压缩之后，复杂度到底是多少？这一块教科书里常写得很学术，但实际结论非常惊人：m 次操作的总复杂度是 O(m α(n))，其中 α(n) 是反阿克曼函数。

反阿克曼函数的增长有多慢？你可以把它理解为“几乎常数”：对任意实际物理世界能遇到的 n，α(n) 都不会超过 4。也就是说，并查集的 m 次操作近似 O(m)，平均每次操作都是常数时间。相比之前的 O(m log n)，这已经是理论和工程上的最优水准。

不过需要小心：这里的“近似常数”是摊还意义下的常数，不是说每一次 Find 都一定是 O(1)。比如第一次对一个还没压缩过的长链做 Find，还是可能走 O(log n) 步。但因为后续操作极大加速，均摊下来就几乎成了常数。

5.4 路径压缩和按大小合并的取舍细节

有个细节值得单独说：使用路径压缩后，每个节点的“树高”会动态变化，原本按大小合并还很精准的“高度信息”不再准确。所以在实际工程里，我不建议在路径压缩的同时用“按高度合并”，而是建议按集合大小（sz）合并。原因很简单：路径压缩后，树的深度变小了，但 sz 记录的是集合元素总数，它是不会因为结构改变而失真的。

如果你想用 rank（秩）来表示树高，注意 rank 只能作为“旧高度”的代称，合并时不必严格同步更新，因为路径压缩后真实高度往往低于 rank。这种情况下按 rank 合并依然是有效的，但理解上稍微绕一点。对大多数场景，按大小合并不仅直观，而且不会因为路径压缩导致信息不对。

6. 常见问题与调试经验实录

6.1 问题的典型症状

实际写并查集时，最常见的几类问题我整理成了一张速查表：

6.2 一个踩过的坑：忘记更新 sz

有段时间我写按大小合并，代码长这样：

if (sz[ra] < sz[rb]) { parent[ra] = rb; } else { parent[rb] = ra; }

看起来没错，但忘了更新 sz。当时数据规模小，跑起来结果都对的。直到后来做了个大规模测试，接近一半的操作出现了诡异行为：合并后树的形状非常差，Find 特别慢。排查了半天，才发现是更新 sz 的语句被漏掉了——size 数组不更新，后面判断大小就全部失真，按大小合并退化成了随机合并。

所以我把这条写进自己的检查清单：Union 里一旦修改了 parent，就必须同步修改对应的 sz 字段。这条不遵守，整个优化就全废了。

6.3 递归版和迭代版怎么选

递归版 Find 写起来非常漂亮，代码只有两三行。但对一个 10 万节点的退化链做第一次 Find 时，递归深度可能到 10 万层，C 语言的默认栈空间大概率顶不住，可能直接栈溢出。

迭代版虽然多写几行，但完全不受调用栈限制。在把这段代码嵌入到服务端程序、或者给一个不知道运行环境底层栈大小的项目用时，我会优先选迭代版。另一个折中方案是：用递归版，同时在程序入口加一个setrlimit提升栈空间限制，或者编译时-Wl,-stack,16777216调整栈大小。但依赖运行环境的东西总是不那么踏实，迭代版更整洁。

6.4 应用场景：不止连通分量

抛开工程细节，这套 Union-Find 结构最经典的应用是动态连通性问题：网络里有 n 台设备，随时可能有设备之间建立连接，也随时要查询两台设备是否连通。并查集做这个几乎是最优解。

另一个高频场景是最小生成树中的 Kruskal 算法：先按边权排序，然后逐条尝试加入边；如果边的两个端点已经在同一个集合里，说明这条边会构成环，不能要。这里判断“是否在同一集合”就需要 Find，合并“把这条边加入生成树”就是 Union。没有并查集，Kruskal 算法的实现复杂度会高一个等级。

再往深走，并查集还能用来维护集合内元素个数、集合内最大最小值（在 sz 之外再维护一些附加信息），甚至可以通过“带权并查集”维护元素之间的相对关系，比如带权值的食物链问题。那一刻你会发现，Union 函数的三次改进并不仅仅是一棵树的变化，而是一整套关于“如何高效维护等价关系”的方法论。

7. 写在最后的实操建议

如果你是自己学或者带新人，我的建议是别急着背最终版代码，而是按本文的节奏把三次改进逐个自己写一遍：先写朴素版，跑一个会退化的数据，观察耗时；再写先 Find 的版本，修正确性；然后加按大小合并；最后加路径压缩。每一步都亲手用“链式 Union”和“查询尾部节点”的测试去体会性能变化。

我个人在实际调试中的一个小习惯是：写一个辅助函数，把 parent 数组的树形结构打印出来，肉眼观察树高。步骤很简单——对每个 i，沿途往根跳，记录步数。跑完 Union 序列后，统计所有节点的深度最大值，如果这个值一直控制在 log n 附近，就说明按大小合并生效了；如果某个时刻突然飙高，那八成是 sz 数组更新漏了，或者合并方向判断写反。

最终版虽然只有十几行核心逻辑，但它融合了正确性、平衡性、压缩性三方面的考虑，值得反复品味。再遇到“判断两个元素是否在一个集合里”“维护动态连通分量”之类的问题，可以直接放心地把它当成默认选项。