Theory · Data Structure · Union-Find / DSU
动态连通性的答案：find / union / connected · 路径压缩 + 按秩合并 → 均摊 α(n) ≈ O(1)
元素不断"抱团"，随时问两个是否同伙——朋友圈 / 连通分量 / 判环
路径压缩（查询时削平）+ 按秩合并（合并时矮的挂高树）
α(n)——阿克曼反函数，宇宙原子数级 n 也 ≤ 4，工程上就是常数
Dynamic Connectivity
① 社交网络：不断加好友，问两人是否间接认识；② 图：加边过程中维护连通分量个数（LC 547 省份数量）；③ 判环：加一条边两端已连通 → 这条边成环（LC 684）。
find(x)：x 所在集合的代表元（根）；union(x,y)：合并两个集合；connected(x,y)：find(x)==find(y)。全部围绕"根"这一个概念。
每个集合是一棵树，parent[i] 指向父节点，根指向自己。所有信息都在 parent 数组里——没有孩子指针、没有键值。
不支持"删除元素"、不支持"拆分集合"（这才是并查集的天花板，也是面试追问点）。
| 实现代际 | find | union | 思路 |
|---|---|---|---|
| Quick-Find（数组染色） | O(1) | O(n) | id[i]=集合号，合并时全改 |
| Quick-Union（森林） | O(h) | O(h) | 挂根；最坏退化成链 O(n) |
| + 按秩合并 | O(log n) | O(log n) | 矮树挂高树，h ≤ log n |
| + 路径压缩（合体） | 均摊 α(n) ≈ O(1)（Tarjan 1975） | ||
Path Compression · Union by Rank
Go Template · 30 Lines
type DSU struct { parent []int rank []int count int // 连通分量数 } func New(n int) *DSU { p, r := make([]int, n), make([]int, n) for i := range p { p[i] = i } return &DSU{p, r, n} } // find：路径压缩（递归版） func (d *DSU) Find(x int) int { if d.parent[x] != x { d.parent[x] = d.Find(d.parent[x]) } return d.parent[x] } // union：按秩合并 func (d *DSU) Union(x, y int) bool { rx, ry := d.Find(x), d.Find(y) if rx == ry { return false } // 已同集合 if d.rank[rx] < d.rank[ry] { rx, ry = ry, rx } d.parent[ry] = rx if d.rank[rx] == d.rank[ry] { d.rank[rx]++ } d.count-- return true }
两趟：先找根，再沿途改指根。压缩后树深极小，递归版实际安全；模板题（LC 547 等）建议迭代版稳妥。
返回"是否真的合并"——判环（684：第二次 false 的边即多余边）、计数（547：count 初值 n，成功合并才减）。
压缩后 rank 虚高、不再等于真实高度，但作为合并依据的上界意义仍成立——"两招不能互相替代"的原因之一。
单独按秩合并：O(log n)；单独路径压缩：均摊 O(log n)；两个一起：均摊 α(n)，任何单招都到不了 α——面试必考的辨析。
Tarjan 1975 · Amortized α(n)
n 次 find/union 操作的总代价 O(n·α(n))——均摊 α(n)。α 是阿克曼反函数：定义 A(1)=1, A(k)=2↑↑(k−2) 的逆——增长快到"逆函数"几乎不动。
α(n) ≤ 4 需要 n < 2^(2^(2^16))——宇宙原子数 (~10⁸⁰) 离这个数还差得远。所以工程口径：α(n) 就是常数 4，"近似 O(1)"。
两种优化互相干扰：路径压缩破坏 rank 的含义、按秩合并限制压缩效果——Tarjan 的势能分析要把两者的交互算清楚。面试只需要结论 + 直觉（"每次 find 都在给后面铺路"）。
这是均摊复杂度：个别 find 可能 O(log n)，但任意操作序列的总账被 α(n) 锁死——与动态数组扩容同属一类保证（复杂度 deck）。
| 优化组合 | 单操作均摊 | 备注 |
|---|---|---|
| 无优化 | O(n) | 最坏退化成链 |
| 只按秩合并 | O(log n) | 确定性保证 |
| 只路径压缩 | O(log n) 均摊 | 最坏单次可 O(n) |
| 两招合体 | O(α(n)) ≈ O(1) | Tarjan 1975 |
Weighted DSU · LC 990
每个节点额外存 val[i] = 相对其父的权值（比值/距离/奇偶…）。find 压缩时沿途权值累乘/累加，把"相对父"重算成"相对根"。
a==b → a、b 权 1 合并；a!=b → 查 find(a)==find(b) 且权值相等则矛盾。变体 399 除法求值：a/b=k 建边权 k，查询即两点权值相除——比建图 BFS 更优雅。
食物链/敌人-朋友问题：把"关系"编码成集合偏移（×2、×2+1 建虚节点），同一套 union/find 逻辑，不需要权值乘法。
题目问的不止"连通"，还有"关系是否自洽"（不等式、比值、传递关系）——信号词："矛盾"、"是否成立"、"推导关系"。
// 带权 find（权值为比值，乘法群） func (d *WDSU) Find(x int) (int, float64) { if d.parent[x] != x { r, w := d.Find(d.parent[x]) d.parent[x] = r d.val[x] *= w // 重算相对根的权 } return d.parent[x], d.val[x] } // union(a, b, k)：a = k · b // fa, wa := Find(a); fb, wb := Find(b) // parent[fa] = fb; val[fa] = k·wb/wa
Where DSU Shines
① Kruskal 最小生成树：边排序后逐条试加，两端不同根才选入（图 deck）；② 连通分量计数（547 省份数量）；③ 判环（684 冗余连接）。
① 账户合并（721）：同邮箱的账户合并成一个集合，最后按集合导出；② 等式约束（990）；③ 字符串等价交换（1202 交换字符串中的元素：可交换位置建并查集，集合内字符排序）。
"动态加边"的连通性：先读完全部操作再回答（离线），比在线结构（LCT）简单一万倍——离线是并查集的隐藏红利。
岛屿数量（200）DFS/BFS 一次搞定；但"动态加陆地"（LC 305 岛屿数量 II）只能并查集——增量语义决定结构选择。
| 题目 | 并查集角色 |
|---|---|
| 547 省份数量 M | count 计数连通分量 |
| 684 冗余连接 M | Union 返回 false 的边 |
| 721 账户合并 H | 邮箱为键合并账户 |
| 990 等式方程 M | 带权/直接合并判矛盾 |
| 128 最长连续序列 M | x 与 x+1 合并取最大集合 |
| 305 岛屿 II（会员） | 动态加陆地的增量维护 |
Practice Path
用 547 练 count 用法、684 练 Union 返回值判环——两题写完，模板的所有字段都有了存在意义。
721 账户合并（map 定位 + 集合导出）、990 等式方程（判矛盾）——学会"把现实关系翻译成合并"。
399 除法求值（比值权）、食物链（种类偏移）——掌握"压缩时维护代数信息"这一层抽象。
① Find 忘记路径压缩（性能腰斩）；② Union 先比较 rank 却比较的是子树大小语义混用；③ count 减在"同集合"分支（应该只在真合并时减）；④ 下标从 1 开始的题没有多开一位。
① 可撤销并查集：只用按秩合并（不压缩）+ 操作栈回滚，离线换根/删边场景；② 可持久化并查集：历史版本查询；③ 最小生成树的 Borůvka/Prim 与 Kruskal 的对比见图 deck。
Interview QA
路径压缩+按秩合并合体后，Tarjan 用势能分析证明均摊 α(n)。α 是阿克曼反函数，n 在可书写范围内恒 ≤4。
行，均摊 O(log n)——压缩会让树越来越扁但合并仍可能长高；配合按秩合并才封顶 α。反之只用按秩合并也是 O(log n)。
不准了（虚高），但作为"合并挂靠方向"的启发式依然有效——这是两招可以共存的微妙之处。
初值 n，每次真合并减一；或最后数根的个数（parent[i]==i）。684 判环、547 计数都靠它。
标准并查集只合不拆。删除的变通：离线倒序处理（把"删"变"加"）、或上 LCT/link-cut tree 这类动态树结构。
边按权排序，逐条取最小：两端不同根 → 选入并 Union；同根 → 跳过（会成环）。直到选满 n−1 条——排序 O(E log E) + 并查集 α(E)。
val[x] 记"x 相对父"的权；find 压缩时沿链做群运算（乘/加/异或）重算为"相对根"。union 时用已知的两点-根权值解出新边权。
静态图一次问完：DFS/BFS 直观；操作序列是"加边+询问"交错（动态）：并查集完胜。200 vs 305 就是分界案例。
Related & References
图算法 →（Kruskal / 连通分量的主场）
排序算法 →（Kruskal 第一步：边排序）
复杂度分析 →（α(n) 均摊的归属语言）
平衡树 →（需要拆分/删除时的替代思路）
Tarjan 1975 · Efficiency of a Good But Not Linear Set Union Algorithm
CLRS ch21 · Data Structures for Disjoint Sets
OI Wiki · 并查集（带权/种类/可撤销章节）
竞赛向：食物链（NOI）、A-B 关系类题集
参考来源（本 deck 结论可溯源至下列一手材料）
| R. Tarjan (1975) · Efficiency of a Good But Not Linear Set Union Algorithm | α(n) 均摊复杂度的原始证明（势能分析） |
| CLRS ch21 | 两招合体的形式化分析（α(n) 引理） |
| LeetCode 547/684/721/990/128 官方题解 | 模板用法、判环、合并导出、带权判矛盾 |
| oi-wiki.org/ds/dsu | 带权并查集/种类并查集/可撤销（中文系统讲解） |
| Galler & Fischer (1964) | 并查集概念的早期论文（equivalence classes） |