并查集：合并、查找与近常数复杂度

一句话定义

并查集（Union-Find / Disjoint Set Union, DSU）用「每个集合一棵有根树」维护不相交集合，支持 find（查所属集合）与 union（合并两集合）；配合路径压缩 + 按秩（或按大小）合并，单次操作均摊 O(α(n))，α 为增长慢到几乎恒为 4 的反阿克曼函数。

为什么重要

它是「只要连通关系、不要路径细节」场景的最优结构：Kruskal 判环、连通分量个数、朋友圈/账户合并、离线动态连通性，实现只要 20 行。它还贡献了本库最漂亮的理论结论之一——Tarjan 1975 证明两优化联合才能达到 α(n)，缺一则界变松；以及一个工程警示——标准 DSU 不支持高效删除（需要可回退/离线变体）。

前置知识

kp-009（映射思想，离散化用哈希）；树的有根表示（kp-011）。

核心概念

• 表示：parent 数组，parent[x] 指向父节点；根指向自身；find(x) 即找根。
• 路径压缩（Path Compression）：find 途中把沿途节点直接挂到根，压平树。
• 按秩合并 / 按大小合并：union 时矮树挂到高树（小树挂到大树）下，控制树高 O(log n)。
• 两优化联合：单次操作均摊 O(α(n))（α(10⁸) < 5）；仅压缩也近线性，仅按秩则 O(log n)。
• 常用扩展：记录集合大小 size[]（合并即相加，可直接数连通分量个数）；带权并查集（边存与根的相对关系，如「食物链」类关系推理）。
• 不支持删除：删点/拆集合需可回退 DSU（离线）或换结构。

直观类比

并查集像「帮派合并」：每个人只记自己的上线（parent），「查是谁的人」就是一路问到话事人（根）；「两帮合并」让一个话事人向另一个低头。路径压缩是「问过一次路的人，从此直接记话事人名字」，帮派迅速扁平化。

原理与机制

标准模板（含双优化与集合大小）：

函数 find(x):
    若 parent[x] ≠ x:
        parent[x] ← find(parent[x])      // 路径压缩
    返回 parent[x]

函数 union(a, b):
    ra ← find(a) ; rb ← find(b)
    若 ra == rb: 返回 false              // 已同集（判环即用这个返回值）
    若 rank[ra] < rank[rb]: 交换 ra, rb
    parent[rb] ← ra                     // 矮树挂高树
    若 rank[ra] == rank[rb]: rank[ra]++
    size[ra] ← size[ra] + size[rb]
    返回 true

α(n) 的直觉：A(i,j) 为阿克曼函数，其反函数增长极慢——宇宙原子数级别输入下 α ≤ 5，故工程上把 O(α(n)) 当常数看待，但要记住它来自「均摊」口径（kp-004），个别单次操作仍可能较贵。

图示

路径压缩前后（find(5) 之后）:
压缩前:                 压缩后:
      1                    1
     /                    / | \ \
    2                    2  3  4  5
   / \                      （沿途全部直挂根）
  3   4
 /
5
判环: 加边 (3,4) 时 find(3)==find(4) ⇒ 成环，拒收。

实例或案例

• Kruskal 求 MST（kp-018）：并查集判环是算法成立的一半。
• 连通分量个数：初始 n 个集合，每成功 union 一次计数减一；LeetCode 547 省份数量、200 岛屿数量。
• 账户合并（LeetCode 721）：邮箱为键做哈希离散化（kp-009）+ 并查集归并同主账户。
• 离线「删边连通性」：时间倒流把删边变加边，DSU 完美适配——离线思想示范。

常见误区

• 只做路径压缩不做按秩（可行但树仍可能深），或反之（O(log n) 达不到 α 界）：两优化联合才有 Tarjan 界。
• union 写反方向（小挂大写成大挂小）或忘记更新 size/rank：统计与复杂度双双失真。
• 以为 DSU 支持高效删除/拆分：不支持，需可回退（按操作栈撤销）或 LCT 级重型结构。
• 键不是整数时忘记离散化：用哈希映射键 → 下标（kp-009）。

自测题

1. 写出含双优化与集合大小的完整并查集模板，并说明 find 的复杂度口径。

答案要点：见机制节；单次操作均摊 O(α(n))，非严格常数，是均摊而非最坏。

1. 「朋友圈」问题：给出 n 人与 m 对朋友关系，如何 O((n+m)α) 数出朋友圈数？

答案要点：初始化 n 个集合，逐条 union，答案 = 成功 union 的次数使集合数递减，最终集合个数；或用 size 统计根的个数。

1. 为什么 Kruskal 可以放心用「find 相同即弃边」判环？

答案要点：同根 ⇔ 已有路径连通，再加边必成环；DSU 恰好维护「当前森林的连通关系」这一不变量。

与其他知识点的关系

kp-018 Kruskal 的判环引擎；kp-016「只要连通性」时的 O(α) 替代（免建遍历）；kp-009 哈希负责键离散化；kp-013 对照——BST 追求全局有序，DSU 只保集合归属，反而更快。

延伸阅读

Tarjan 1975 论文；《算法（第 4 版）》第 1.5 节（含加权 quick-union 的实验对比）；CLRS 第 21 章「用于不相交集合的数据结构」。