并查集（进阶）
复习
- 连通分量与环：判断节点之间是否连通
- 图：由节点和边组成
- 树：用父子关系表示层次
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 并查集维护“哪些元素属于同一组”
- 它支持合并两组、查询是否同组
- 用树表示组，路径压缩与按秩合并让它极快
- 它几乎是“连通分量”的专用工具
正文
有时候，我们不关心路径有多长，只关心一个更简单的问题：这两个元素是不是在同一组里？ 而且还会不断有“把两组并起来”的操作。
专门为这种需求设计的结构，叫并查集（union-find，或 disjoint set）。
只回答两个问题
并查集对外只提供两个核心操作：
- 查找（find）：一个元素属于哪一组（用某个代表元来标识这一组）
- 合并（union）：把两个组合并成一个
有了这两个操作，就能回答“两人是不是朋友的朋友”这类问题：只要看他们的代表元是不是同一个。
用树来表示组
并查集内部通常用树来表示每一组：同组元素共享同一个根，这个根就是这一组的代表元。
- 查找：沿着父指针一路向上，找到根 - 合并：让一棵树的根指向另一棵树的根
于是，“是不是同一组”就变成了“根是不是同一个”。
两个让它飞快的技巧
朴素的做法可能让树变得很高，查找就慢了。两个经典优化能把它压到几乎 O(1)：
- 路径压缩：查找时，顺手把沿途的节点直接挂到根上，让树变扁。以后再查这些节点，一步就能到根
- 按秩／按大小合并：合并时，把矮的树接到高的树上，避免树越接越高
这两个技巧配合起来，操作的平均代价几乎是常数，非常高效。
它用在哪
并查集特别适合处理动态连通性：随着边一条条加进来，不断回答“现在这俩连通了吗”。
它也正是下一章最小生成树算法（Kruskal）里的关键零件——用来判断“加这条边会不会成环”。一个专精的小工具，往往能在更大的算法里发挥关键作用。
思考题 1
并查集解决的是什么问题？它和“连通分量”有什么关系？
思考题 2
路径压缩为什么能让并查集变快？
小结
知识点
- 并查集维护分组与合并、查询操作
- 用树表示组，根为代表元
- 路径压缩与按秩合并使它近乎常数时间
- 适合动态连通性与 Kruskal 算法
参考资料
- Wikipedia(zh)：并查集：维护不相交集合的数据结构
- Wikipedia(zh)：连通分量：并查集常用于动态维护连通性
思考题答案（仅供参考）
思考题 1
它解决的是“元素分组”的问题：支持把两组并起来，以及查询两个元素是否同组。随着边不断加入，它正好可以动态维护图的连通分量，判断两个节点是否连通。
思考题 2
因为查找时把沿途节点直接挂到根上后，树变得非常扁，之后这些节点的查找几乎一步就能到达根。树越扁，后续操作越快，路径压缩正是通过不断把树压扁来提升整体效率。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪