并查集

并查集维护若干不相交集合，反复回答“两元素是否已经连通”。union(a, b) 合并它们所属的集合，find(x) 返回集合代表元。两个 find 结果相同，才属于同一集合。按秩合并与路径压缩结合后，每次操作的摊还时间为 O(α(n))，实际规模下接近常数。

Kruskal 最小生成树用它判断加边是否成环：只有端点属于不同集合才接入。它也用于无向图环检测、连通分量计数、渗流模型和只增加连接的网络查询。

parent[i] 保存元素 i 的父节点。parent[i] == i 时，i 是根，也是集合代表元。集合用树表示，多个集合构成森林。find 沿父指针到根，优化的目标是缩短这些路径。

按秩合并与路径压缩

find(x) 反复读取并跟随 parent[x]，直到节点指向自己。

union(a, b) 先分别 find。根相同就无需合并；否则让一个根指向另一个根。

朴素实现固定写 parent[find(a)] = find(b)。依次 union(0,1)、union(1,2)、union(2,3) 会接成链，每次多一层，后续查找最坏要走 O(n)。

两项优化控制形状：

• 按秩合并：根保存 rank，作为高度上界。较小秩的根接到较大秩下，秩不同则不增秩；秩相等时，胜方秩加一。达到秩 h 至少需要 2ʰ 个元素，因此单用按秩合并就能把高度控制在 O(log n)。压缩后秩不必等于当前实际高度。
• 路径压缩：find 找到根后，把访问路径上的节点直接指向根。第一次支付的遍历成本会减少后续重复查找；若之后没有合并改变根关系，被压缩节点下次只需一跳。

两者结合的摊还界为 O(α(n))。α 是反阿克曼函数，在实际可处理的输入规模中小于 5。它增长极慢，但理论上不是常数。

逐步演示

默认 Optimized，六个元素 0 到 5 各自成集。parent[] 每格指向自己。演示依次执行 union(0,1)、union(2,3)、union(4,5)、union(0,2)、union(0,4)，最后两次 find(5)。

1. union(0,1)：两根秩都为 0，平局由第一个根获胜。parent[1] 从 1 改为 0，0 的秩升为 1。
2. union(2,3)、union(4,5) 同样处理。得到根为 0、2、4 的三棵双节点树，根秩均为 1。
3. union(0,2)：秩再次相等，2 接到 0 下，0 的秩升为 2。0 直接连接 1、2，2 仍连接 3，所以 3 深度为 2。
4. union(0,4)：秩为 2 与 1，4 接到 0 下，0 不增秩。全部元素属于根 0，3、5 位于深度 2。
5. 第一次 find(5)：读取 parent[5] = 4，再读 parent[4] = 0，0 指向自己。找到根后，把 parent[5] 从 4 改为 0。画布边向上转，数组同步更新，5 从深度 2 变为根的直接孩子。
6. 第二次 find(5)：只需一跳到 0，无需进一步压缩。相同查询的路径已经缩短。

切换 Naive，运行链式 union(0,1)、union(1,2) 等，再 find(0)。可以看到树逐段变高，查找走完整高度，没有压缩。

时间与空间复杂度

核心存储为 parent 数组，优化版另有 rank，无需逐节点对象或孩子指针。单用秩可得 O(log n)；单用压缩能缩短已访问路径，但不能直接套用两者结合的反阿克曼界。

也可按大小合并：记录各集合元素数，把小集合接到大集合下。与路径压缩结合时有相同渐近界。选择一种策略并一致维护。

边界情况

• 合并已连通元素：两个 find 得到同根，不再合并。优化代码提前返回，朴素代码只做无害的自赋值；find 自身仍可能压缩路径。
• 查根：零次跳转，立即结束，无需压缩。
• 查根的直接孩子：一跳，链接已最短。
• union(a, a)：属于同根情况。
• 未参与合并的单元素：保持独立；只有两个不同集合真正合并，集合数才减少。

常见错误

• 比较 parent[a] 与 parent[b]。 同集元素可以有不同父节点；要比较根，即 find(a) 与 find(b)。
• 把大秩树接到小秩树下。 会增加不必要的高度，破坏按秩策略。
• 每次 union 都增秩。 只有不同的同秩根合并时，胜方才加一。
• 要求压缩后秩等于树高。 压缩降低实际高度，却不减秩。秩仍是有效上界，不必重新遍历计算精确高度。
• 用并查集删除边或拆集合。 普通并查集只合并。连接删除需其他结构，或在适用问题中离线逆序处理。