作为常年和算法打交道的开发者我特别理解很多人在学到并查集Disjoint Set Union简称 DSU时那种“原理好像懂了代码好像也抄过但换个场景就不会用了”的尴尬。这个概念在面试、竞赛和实际工程项目里出现频率极高尤其是涉及网络连通性、社交关系分组、动态连通性判断这类需求时它几乎是性能最优的解法之一。这篇内容我会把并查集从底层原理到工程实现彻底拆开讲透适合刚接触数据结构的新手也适合学过但一直没真正吃透的进阶读者。我不会像教科书那样上来就丢公式而是用一个大家都能理解的生活场景切入然后一步步把它背后的设计逻辑、优化手段、常见误区全部展开。你可以把它当成一份带注释的源码级笔记既能帮你应付面试八股也能让你在真实项目里敢于直接用。1. 并查集到底在解决什么问题1.1 一切从一个关系问题开始先想象一个场景一个社交平台上有 N 个用户平台需要判断任意两个用户之间是否存在“好友链”。所谓好友链不要求两个人直接是好友只要 A 和 B 是好友、B 和 C 是好友那么 A 和 C 就在同一个关系圈里。这时候系统要快速回答用户 X 和用户 Y 是否在同一个圈子里如果你用最朴素的想法建立一个 N×N 的布尔矩阵记录两两关系那每新增一条好友关系可能都需要遍历大量条目。当 N 达到百万甚至千万级别这个矩阵彻底不可行——光是存储就爆炸了。这就引出了需要解决的核心问题我们只关心两个元素是否“连通”在同一个集合里并且允许动态地添加新的连通关系。并查集就是为这种“动态连通性”场景设计的数据结构它用非常小的空间代价O(N) 级别实现了接近 O(1) 的操作速度。1.2 并查集的核心能力其实就两件事很多人把并查集想得很复杂其实它对外暴露的能力极其简单本质上就是两个操作find和union。find(x)用来查询元素 x 属于哪个集合在实现上通常是找到这个集合的“代表元”可以理解成圈子的群主。union(x, y)用来把 x 和 y 所在的两个集合合并成一个。第三个常见操作isConnected(x, y)则是查询 x 和 y 是否在同一个集合这个操作等价于判断find(x) find(y)。你可能会觉得这太简单了但恰恰是这两个看似基础的操作构成了许多复杂算法的地基。Kruskal 最小生成树算法用它来判断两个顶点是否已经连通图像处理里用它做连通域标记编译器用它来管理变量的等价类。可以说凡是涉及“分组 合并 查询”的问题都可以优先考虑并查集。2. 核心设计思路底层为什么长这样2.1 从“谁属于谁”到“一棵树”初学者最容易困惑的一点是并查集内部到底怎么表示集合最直觉的想法是每个集合用一个链表或者动态数组存元素。合并两个集合时把一个数组的元素全部拷贝到另一个数组里去。听着似乎可行但每次合并的代价是 O(N)在频繁合并的场景下算法会退化到不可用。并查集的巧妙之处在于它反其道而行之不是记录“集合里有哪些元素”而是记录“每个元素认谁做父节点”。每个集合被组织成一棵多叉树树的根节点就是这个集合的代表元。底层存储只需要一个parent数组parent[i]表示元素 i 的父节点索引如果parent[i] i说明 i 就是所在集合的根节点。用这棵树的思维方式查询操作就从 O(N) 降到了 O(树高)。理论上树高最坏是 O(N)比如每次都是深度加一的链式合并但通过后续的优化手段树高会被压得非常低几乎可以认为是常数。2.2 为什么“向上找根”比“遍历集合”更快想象你有一个微信群群里每个人只知道自己拉进群的上一个人不是群主。想知道两个人在不在同一个群你只需要沿着“我拉了谁、谁拉了我”这条链一直往上报直到报到群主那里。如果两个人的群主是同一个人那就在一个群里。这就是find操作的朴素实现。它不需要记住群里所有成员只需要记住“上一级”是谁所以空间占用极小合并两个群时也只需要改一个指针把一个群的群主认另一个群主当爹。相比之下如果“群主”需要维护一个所有成员的通讯录那每次拉新人或者合并群都要重新整理通讯录代价就会大幅上升。这就是为什么并查集选择了“只记录父节点”而不是“记录全部子节点”的核心原因。2.3 第一次优化路径压缩Path Compression朴素实现里有个致命问题如果合并顺序不巧树会变得很高。比如你连续执行union(1,2)、union(2,3)、union(3,4)如果每次都把后一个节点接到前一个节点上就会形成一条 1→2→3→4 的链。此时查找元素 4 的根需要向上爬 3 层随着元素增多查询会越来越慢。路径压缩的思路非常聪明既然我们在find(4)的过程中已经经过了 4、3、2 这条路径那就顺便把这条路径上所有节点的父节点直接改成根节点。下次再查 3 或 2 时一步就能跳到根。用一句话总结查完之后把沿途所有节点直接挂到根节点下。这不会让数据结构变“错”反而会让树越来越扁之后的查询越来越快。路径压缩是“懒”出来的优化——它不提前整理只在每次查询时顺手修路。2.4 第二次优化按秩合并Union by Rank路径压缩解决的是“查询后变快”的问题但树的高度仍然可能因为合并顺序而变得不理想。既然两个集合要合并那就应该尽量把矮的树接到高的树上避免树的高度继续增加。这里的“秩”Rank通常是树的高度或者集合大小。按秩合并的核心规则始终把秩较小的根节点接到秩较大的根节点下面。如果两棵树的秩相同合并后新树的秩加一。你可能会问有了路径压缩按秩合并还有必要吗有必要。路径压缩只影响查询过的节点如果一个节点长期不被查询它的层级仍然会很深。按秩合并在合并时就从源头上控制树高两者配合才能达到几乎 O(1) 的最优效果。业界把这套组合称为“并查集的标准实现”几乎所有高并发下的动态连通性判断用的都是它。3. 代码实现与实操细节3.1 先写一个最朴素的版本我直接给出一个可运行的 Python 版本把注释写详细。这里的代码没有做任何优化目的是让你理解框架本身。class DSUBasic: def __init__(self, n: int): # 初始化时每个元素单独成一个集合自己就是自己的根 self.parent list(range(n)) def find(self, x: int) - int: # 不断向上找根直到 parent[x] x while self.parent[x] ! x: x self.parent[x] return x def union(self, x: int, y: int) - None: rx self.find(x) ry self.find(y) if rx ry: # 已经在同一个集合 return # 把 rx 所在集合合并到 ry 所在集合注意方向不重要 self.parent[rx] ry def is_connected(self, x: int, y: int) - bool: return self.find(x) self.find(y)这个版本能跑但在最坏情况下性能较差。比如在一个线性合并场景里find的复杂度可能是 O(N)总复杂度就变成 O(N²)数据量一大就会超时。实际工程里我们不会用这个版本但理解它是理解后续优化的起点。3.2 标准优化版路径压缩 按秩合并下面这个版本是我在实际开发中一直在用的模板综合了前面讲到的两种优化class DSU: def __init__(self, n: int): self.parent list(range(n)) self.rank [0] * n # 记录树的高度秩 self.count n # 当前集合数量维护它方便查询总簇数 def find(self, x: int) - int: # 递归写法更直观但注意 Python 默认递归深度限制 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def find_iterative(self, x: int) - int: # 不依赖递归的版本工程里更稳妥 root x while self.parent[root] ! root: root self.parent[root] # 第二次循环实现路径压缩把路径上的节点全部直接挂到 root 下 while self.parent[x] ! x: nxt self.parent[x] self.parent[x] root x nxt return root def union(self, x: int, y: int) - bool: rx self.find_iterative(x) ry self.find_iterative(y) if rx ry: return False # 合并失败因为本来就在同一集合 # 按秩合并矮树接高树 if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 self.count - 1 return True def is_connected(self, x: int, y: int) - bool: return self.find_iterative(x) self.find_iterative(y)这里有几个细节值得展开。第一个细节是为什么通常只维护每个根节点的秩而不是维护所有节点的秩。因为秩只在合并时用来决定谁当根路径压缩并不会改变根节点的秩所以非根节点的秩没有用省下这个更新成本是合理的。第二个细节是count这个变量。很多教程不会提它但在实际项目中分组数量是一个经常需要获取的信息。比如社交网络里有多少个独立的圈子、连通域标记里有多少个区域有了count就可以直接返回self.count而不需要每次遍历parent数组去数根的数量。这是低成本高收益的设计。第三个细节是递归写法虽然看起来简洁但在 Python 里受递归深度限制影响。当集合规模超过 1000 时递归深度可能不够用所以我更推荐迭代版find。我遇到过几次递归版本在线上环境递归深度溢出的问题切换到迭代版后问题彻底消失。3.3 复杂度到底是多少为什么能接近 O(1)并查集的复杂度分析是个很有意思的话题。你很难用一句话精确表达因为它和操作顺序以及优化方式有关。在不做任何优化的情况下find的复杂度是树高最坏 O(N)。加上了路径压缩和按秩合并之后单次操作的均摊复杂度反比于一个增长极慢的函数——Ackermann 函数的反函数 α(n)。这个函数在 n 等于宇宙原子数量时它的值也不会超过 4。所以在实际工程中可以放心地把并查集的单次操作看作是 O(1)。换句话说做 N 次操作的总复杂度是 O(N·α(N))本质上就是 O(N) 级别。这也是为什么在百万甚至千万级节点的场景下并查集依然是主流选择。3.4 初始化时的常见决策数组大小与索引偏移写代码之前需要先确定数组长度。大多数情况下我们使用 0 到 N-1 的索引但实际业务里的元素可能是用户 ID、坐标点、数据库主键这些值可能很大且不连续无法直接作为数组下标。我的惯用做法是引入一个 ID 到索引的映射表。先把所有原始 ID 编码成 0 到 N-1 的连续整数再做并查集。这个过程通常可以用字典HashMap来完成。另一个常见做法是使用哈希并查集底层不存连续的数组而是用字典dict来存父节点关系。这样即使元素很稀疏也能按需创建节点缺点是常数因子比数组大。如果数据范围可控数组版始终是性能首选。4. 常见问题与排查技巧实录4.1 忘记路径压缩导致 TLE我有一次在 LeetCode 上写一道并查集题本地测试用例全过一提交就超时。后来排查发现我的find写的是朴素版本没有路径压缩。数据量一上来查找路径越来越长就卡死了。排查技巧其实很简单如果你并查集题目的数据范围超过 10^5而你的代码超时第一反应就是检查find是否做了路径压缩。这是最常见也最容易忽略的问题。另外要注意递归版本的路径压缩写法有个隐患如果在递归之前没有self.parent[x] self.find(self.parent[x])这行树永远不会被压扁。4.2 合并方向看似无所谓但会影响秩很多初学者觉得union(rx, ry)里谁接谁都一样反正查连通性不受影响。这在逻辑上没错但会影响树的高度进而影响性能。如果你总是把新集合挂到旧集合下面不按秩合并树的形状可能会越来越差。我在带新人时经常强调一定要写完整的按秩合并逻辑别图省事省略。虽然路径压缩能在很大程度上弥补树高的问题但两者结合的稳定性远高于只用路径压缩。实测下来在大规模随机合并场景下二者结合的查询耗时只有只用路径压缩的约三分之一。4.3 递归深度溢出Python 的默认递归深度限制是 1000 左右。当你的并查集树在极端情况下的深度超过 1000递归版find就会直接抛RecursionError。即使没超过频繁递归的调用开销也比循环大得多。我建议在 Python 里直接使用迭代写法的find代码如下参考前面给出的find_iterative。这套写法用两次循环完成“找根”和“压缩”两件事逻辑上稍复杂但更稳健。如果非要用递归可以在文件开头加sys.setrecursionlimit(1 20)这是一个临时方案但不能从根本上解决性能问题。4.4 常见问题速查表症状可能原因解决方案递归时栈溢出树高较大且使用递归查找改用迭代版find大量操作超时缺少路径压缩或按秩合并确认两种优化都已实现连通性判断错误初始化parent数组时范围写错检查数组长度是否为 N特别是动态添加节点时合并之后count不变忘了在union里更新count合并成功时将计数减一下标越界输入数据不是从 0 开始增加偏移映射或调整数组大小4.5 一个折腾了我一晚上的坑路径压缩后的秩失真按秩合并中的秩保存的是树的高度的近似值但在路径压缩后有些节点被直接挂到了根下它们原有的高度记录已经不准了。我有一段时间为了追求“更准确”尝试在路径压缩时去更新秩结果发现代码复杂了很多性能也没有明显提升。后来我想明白了秩只是一个合并时的启发式标记它不需要精确。即使有些失真按秩合并依然能保证合并后树的高度不会失控。与其去修正秩不如放任它让路径压缩帮你兜底。这是个需要经验才能想通的点。5. 应用场景与并查集的进阶变体5.1 经典问题朋友圈数量题目通常是这样给定 N 个人和 M 对好友关系问最终能形成多少个朋友圈子。这本质上就是把所有人初始化为独立集合然后把每条好友关系作为一次union操作。最终count的值就是朋友圈数量。如果你维护了count变量这道题的核心代码不超过二十行。这也是我为什么在前面强调要实现count的原因——面试官特别喜欢追问“怎么快速知道还有多少个集合”。5.2 经典问题判断图中是否存在环在无向图中判断是否成环也可以用并查集。核心思路是遍历每条边如果边的两个端点已经在同一个集合里即已经连通那么这条边就是多余的图中存在环。如果不在同一集合就执行union把它们连通。这个方法的时间和空间效率都优于朴素的 DFS 或 BFS 方案而且实现简单。尤其是配合 Kruskal 算法求最小生成树时这个特性几乎是标配。5.3 带权并查集处理“相对关系”标准的并查集只维护“是否连通”有时需求引申到“节点之间的距离关系”。比如在食物链问题里A 吃 B、B 吃 C、C 吃 A需要判断给定的关系是否为假。这种场景就要用带权并查集。它在每个节点上额外维护一个到父节点的权值find的时候累加权值union的时候通过权值关系计算新的偏移量。权值的含义完全由业务定义可以是取模值也可以是具体的长度或差异。它的核心设计还是并查集的框架只是在“维护连通性”之上多维护了一层相对关系。5.4 可撤销并查集支持回滚还有一种变体经常出现在竞赛和算法题里可撤销并查集。它要求支持union操作之后再撤销最近一次合并。使用这种变体时为了保证可回顾合并时不能做路径压缩因为路径压缩会破坏原来的父子关系导致回滚时无法准确恢复。通常只使用按秩合并并把每一次合并涉及的节点和秩变化压入栈中撤销时从栈中取出记录反向恢复即可。理解路径压缩为什么会在可撤销并查集中禁用能反过来加深你对路径压缩本质的理解它用“修改历史结构”换取了查询加速这在大部分场景里是划算的但在需要保留操作历史的场景里会带来麻烦。5.5 实战项目里的一个用法服务器连通域检测我在做分布式系统监控的时候用并查集做过一个功能输入每台服务器之间的网络连通记录动态判断任意两台服务器之间是否存在可达路径。当时数据量是数万台服务器连边记录每秒都在新增。如果用图的不变式判断每一步都要重算全量连通性开销非常大。后来我改造成并查集每新增一条连边就做一次union每收到一个查询请求就做两次find耗时从秒级降到了微秒级。这次实践让我确信并查集不是只活在面试题里的数据结构它在真实工程里同样能发挥巨大价值。5.6 并查集与“反集”技巧“反集”是并查集在处理“敌人关系”时的一个技巧。比如有 N 个人已知一些“敌对”关系要求保证“敌人的敌人是朋友”并判断是否存在矛盾。实现时把每个人拆成两个节点i 表示自己i N 表示 i 的“敌人集合”。如果 a 和 b 敌对就把 a 与 b N 合并把 b 与 a N 合并。这种构造在处理“染色”类约束问题时非常常见。我第一次看到反集时觉得挺玄学但仔细想想它利用的仍然是并查集“合并”和“查询”的原子能力只是把关系映射到了两倍的空间里。掌握了基础原理之后这类变体理解起来会顺畅很多。6. 个人经验谈什么时候该用并查集很多人学完并查集后反而陷入了“拿着锤子找钉子”的状态遇到什么题都想套并查集。这里我分享两个判断标准。第一个标准是看操作类型。只要问题里出现了“将两个集合合并”和“判断两个元素是否属于同一集合”这两种操作就可以考虑并查集。如果只有查询没有合并那可能是静态图的可达性问题更适合用 DFS 或 BFS。第二个标准是看数据规模。并查集在千万级数据下依然能保持极低的延迟但前提是初始化数组和做映射都合理。如果数据量极小比如几十个元素用并查集反而有点大材小用朴素方法就足够了。我个人的建议是把并查集模板作为一种固定的“工具箱”存在本地遇到连通性、分组、等价关系类问题时先画出操作表看看是否匹配find和union的模型。匹配就直接套模板这样能节省大量思考时间。最后再分享一个小技巧。面试或写题时写并查集代码之前先和面试官把parent数组的语义讲清楚“parent[i]表示 i 的父节点根节点满足parent[i] i”。这一句话能节省很多解释成本也能让考官立刻确认你真的理解原理而不是在背模板。写代码时把find、union、is_connected三件事拆得清清楚楚调试时也能更快定位问题。