并查集：连通性问题的高效解法
数据结构学到这里，你会慢慢发现：并不是所有问题都在问“怎么查找某个值”“怎么维护顺序”“怎么取最小最大”。还有一类问题问得非常直接，也非常高频：两个元素是不是属于同一组？一堆对象之间是否连通？加入一条边之后，哪些点被合并到了同一个集合里？
这类问题如果每次都现算图遍历，当然也能做，但代价往往偏高。并查集之所以经典，就是因为它专门为这类“动态维护若干不相交集合，并快速判断归属关系”的问题设计。它不是传统意义上最直观的树或表结构，但它在图算法、网络连通性、社交关系分组、最小生成树等场景里非常高频。
所以学并查集时，最重要的不是把几个函数名记住，而是先看清它到底解决什么问题：
一边不断合并集合，一边高效判断两个元素是否已经属于同一集合。
一、什么是并查集
并查集，英文通常叫 Disjoint Set Union，简称 DSU 或 Union-Find。它维护的是若干个互不相交的集合，并支持两类核心操作：
find(x)：查找元素x所属集合的代表；union(x, y)：把x和y所属的两个集合合并。
如果两个元素 find 出来的代表相同，就说明它们已经属于同一个集合。
所以并查集最本质的事情是：
- 管理分组；
- 支持合并；
- 快速判断是否同组。
二、为什么普通结构不够高效
假设你有很多元素和一些连接关系，想不断回答：
a和b连通吗？- 加入这条连接后，原来的两个集合是否应该合并？
如果每次都：
- 重新做一次
DFS/BFS； - 或者暴力扫描整个分组信息；
那么在大量动态合并场景下，成本会很高。
并查集的价值就在于：
- 让集合合并变得局部可维护；
- 让连通性判断几乎接近常数时间。
三、并查集通常怎么表示集合
并查集最经典的底层思路，是用一棵树来表示一个集合。
- 每个元素是一个节点；
- 每个集合对应一棵树；
- 树根可以看作这个集合的代表元。
于是：
find(x)就是一路向上找到根；union(x, y)就是把一棵树的根接到另一棵树根上。
所以并查集虽然名字里有“集”，但它底层其实常用森林结构来维护。
四、什么是代表元
代表元可以理解成：
当前集合的一个标识节点，通常就是树根。
它并不一定携带特别业务语义，关键作用是：
- 作为集合身份的统一标记；
- 只要两个元素找到同一个根，就说明它们同组。
所以并查集判断连通的核心逻辑特别简单：
1 | find(x) == find(y) |
五、并查集最基本的三种操作
1. 初始化
一开始，每个元素各自属于一个独立集合，也就是每个节点自己是自己的根。
2. 查找 find
从当前节点一直沿父节点往上，直到找到根节点。
3. 合并 union
先分别找到两个元素的根；
如果根不同，就把一个根挂到另一个根下面，完成集合合并。
这三个动作构成了并查集最基础的工作流。
六、为什么朴素并查集还不够快
如果你只是简单地把一个根挂到另一个根下面，树形可能会越来越高。
例如如果总是：
- 把新集合接到某个固定根下；
- 或者形成一条长链；
那 find 操作就会变慢，因为每次都要走很多层。
所以并查集真正高效，靠的不是最朴素版本，而是两个关键优化：
- 路径压缩；
- 按秩合并或按大小合并。
七、什么是路径压缩
路径压缩的核心思想是：
在执行
find(x)的过程中，顺手把路径上的节点都直接挂到根上。
例如你原本从 x 找根，需要走很多步；那找完之后，不妨把这一路上的节点父指针都改成根。这样下次再查这些节点时，路径就会短很多。
这是一种典型的“查询时顺手优化结构”的思路。
它的意义非常大，因为在大量连续操作中，路径压缩能让树迅速扁平化。
八、什么是按秩合并或按大小合并
这类优化的目标是：
合并时尽量别让树长得太高。
常见做法有两种：
1. 按大小合并
把小集合挂到大集合根下面。
2. 按秩合并
把高度较低或近似层数较小的树，挂到更高的树下面。
不管是哪一种，本质上都是在尽量控制树高增长。
九、路径压缩和按秩合并一起用会怎样
这正是并查集之所以强大的原因。
- 按秩合并从源头上减少树变高的机会；
- 路径压缩在查询过程中进一步把树压平。
两者一起使用后，并查集的单次操作复杂度在均摊意义上可以做到非常接近常数时间。严格分析会涉及反阿克曼函数，但在实际应用里通常可以把它看成“几乎 O(1)”。
所以并查集之所以在图论和连通性问题里高频，不是因为它花哨，而是因为它真的很高效。
十、并查集最典型的应用场景有哪些
1. 动态连通性判断
给定若干点和连接操作，反复问两个点是否连通。
2. 图中连通分量维护
不断合并边连接的点，最后统计有多少个连通块。
3. Kruskal 最小生成树
这是并查集最经典的算法应用之一。每加入一条边前，只要判断两个端点是否已在同一集合，就能知道这条边会不会形成环。
4. 社交关系、群组归并
谁和谁属于同一圈子、同一组织、同一连通网络。
5. 等价类问题
例如多个对象通过若干关系被判定为“同类”。
这些问题共同的味道就是：
- 不断合并；
- 不断问是否同组。
十一、并查集和图遍历是什么关系
它们都能处理连通性问题，但适用场景不同。
1. DFS / BFS
更适合：
- 你已经有完整图结构；
- 想从一个起点遍历整块区域；
- 或者想拿到具体路径、访问顺序。
2. 并查集
更适合：
- 你关心的是“是否同组”；
- 连接关系在动态加入；
- 需要高频判断集合归属。
所以并查集并不是“替代图遍历”，而是专门针对连通性维护做优化的一种结构。
十二、并查集有什么局限
1. 不擅长删除关系
经典并查集很适合合并，不适合把已经合并的集合再拆开。
2. 不直接给出路径信息
它只告诉你是否属于同一集合，通常不告诉你具体怎么连通。
3. 更适合静态或单向增加连接的场景
如果关系频繁增删，需要更复杂的数据结构。
这说明并查集虽然高效，但优化得非常专注：
它擅长的是“合并 + 判断同组”，而不是所有图问题。
十三、学习并查集时最容易踩的坑
1. 只会背模板，不理解集合树表示法
如果不理解“每个集合是一棵树”，很多优化就会显得像魔法。
2. 忘记先找根再合并
union 的核心是合并代表元，不是随便把两个普通节点连起来。
3. 不理解路径压缩为什么正确
路径压缩不会改变集合归属，只是在保持代表元不变的前提下缩短查询路径。
4. 把并查集用到需要删除和精确路径的问题上
这超出了它的强项。
总结
并查集的重要性，不只是因为它在算法题里高频，而是因为它把“动态维护连通性”这件事抽象得非常高效。真正值得先建立起来的，是这些核心认识：
- 并查集维护的是若干互不相交的集合；
find负责找到代表元，union负责合并集合；- 用森林表示集合后，连通性判断可以转化为“是否同根”；
- 路径压缩和按秩合并，是并查集高效的关键；
- 它特别适合动态合并和同组判断问题，例如 Kruskal、连通块维护、等价类归并；
- 真正学会并查集，不是背一段模板，而是知道它到底在优化什么、又不擅长什么。
把这一篇理解透之后，后面再去学图算法时，你会更容易看清：有些问题需要遍历整张图，有些问题只需要维护“是不是连着”。而后者，正是并查集最擅长的领域。
参考资源：