并查集从入门到实战：路径压缩与按秩合并详解

1. 并查集到底在解决什么问题第一次接触并查集是在刷一道连通性问题的时候题目给了一堆节点和边要求判断任意两个节点是否属于同一个集合。当时第一反应是用图搜索每次查询都跑一遍BFS或者DFS结果数据量一上来直接超时。后来看到题解里有人用了一个叫“并查集”的东西代码短得离谱查询几乎是常数时间我才意识到这个数据结构的设计有多巧妙。并查集英文叫Union Find也有人叫它Disjoint Set UnionDSU翻译过来就是“不相交集合的合并与查询”。它的核心能力就两个合并两个集合和查询两个元素是否在同一个集合里。听起来简单但这两个操作在实际问题中出现的频率极高比如判断网络中的节点连通性、检测图中的环、分组聚类、动态维护等价关系等等。它适合谁来学只要你有基本的数组操作基础能理解递归或者迭代就能学会并查集。它的代码量非常小核心逻辑不超过二十行但背后的优化思想值得反复琢磨。不管你是刚学算法的新手还是已经工作几年但没系统整理过数据结构的开发者并查集都是一个投入产出比极高的知识点。这篇文章我会从设计思路、核心实现、优化技巧、常见坑点几个方面把并查集彻底讲透。不是那种教科书式的定义堆砌而是像一个写过很多遍并查集的人把自己踩过的坑和总结的经验一次性倒出来。2. 并查集的核心设计思路拆解2.1 为什么用“树”来表示集合并查集最直觉的实现方式是用一个数组parent[i]表示元素i的父节点。如果parent[i] i说明i是这个集合的根节点也就是代表元素。同一个集合里的所有元素最终都会指向同一个根。为什么用树而不是链表或者哈希表因为树结构在合并操作上有天然优势。两个集合合并时只需要把一棵树的根挂到另一棵树的根下面一步操作就完成了不需要遍历整个集合。如果用链表合并时得把一条链的所有节点都改一遍效率差很多。你可以把并查集想象成一群人在组队。每个人一开始都是自己的队长parent[i] i。当两个人决定组队时其中一个人的队长就变成另一个人的队长。随着不断组队最终每个人都能追溯到自己的“总队长”。查询两个人是不是一队就看他们的总队长是不是同一个人。2.2 路径压缩让查询越来越快最朴素的并查集有一个问题如果合并的时候总是把A挂到B下面B挂到C下面C挂到D下面树就会退化成一条链。这时候查询最底下的节点得一路往上爬时间复杂度退化成O(n)。路径压缩就是解决这个问题的。它的思路很直接在查询某个节点的根节点时顺便把沿途所有节点的父节点直接改成根节点。这样下次再查这些节点一步就能找到根。举个例子假设树是1 - 2 - 3 - 44是根。查询1的根时路径压缩会把1、2、3的父节点全部直接设为4。树变成了1 - 4、2 - 4、3 - 4高度从4降到了2。再查一次就是O(1)了。路径压缩的实现通常用递归def find(x): if parent[x] ! x: parent[x] find(parent[x]) return parent[x]递归的写法很简洁但要注意递归深度。如果数据量特别大递归可能导致栈溢出。这时候可以改成迭代版本def find(x): root x while parent[root] ! root: root parent[root] # 路径压缩 while parent[x] ! root: parent[x], x root, parent[x] return root迭代版本稍微绕一点但更安全。我个人在实际写题的时候如果数据量在10^5以内递归完全够用如果上到10^6甚至更大我会换成迭代版本。2.3 按秩合并不让树长歪路径压缩解决的是查询效率按秩合并解决的是合并效率。所谓“秩”可以理解为树的高度或者集合的大小。合并两个集合时把秩小的树挂到秩大的树下面这样树的高度增长最慢。为什么这样做有效假设两棵树高度分别是h1和h2如果h1 h2把h1挂到h2下面新树高度还是h2反过来把h2挂到h1下面新树高度就变成h11。显然前者更优。按秩合并通常用一个rank数组来记录每棵树的高度或者用size数组记录集合大小。合并时比较两个根的rank小的挂到大的下面。如果rank相同随便挂一个然后被挂的那个根的rank加一。路径压缩和按秩合并一起用的时候理论时间复杂度可以降到接近O(1)具体来说是O(α(n))其中α是阿克曼函数的反函数增长极其缓慢对于任何实际能遇到的数据量α(n)都不会超过5。所以你可以认为并查集的操作就是常数时间。注意路径压缩和按秩合并同时使用时rank数组的含义会变得模糊因为路径压缩会改变树的结构。有些实现会用size代替rank效果类似。我个人更倾向于用size因为size在合并时更直观而且不会因为路径压缩而失真。3. 并查集的完整实现与关键细节3.1 基础版本十行代码搞定先来看一个最基础的并查集实现不带任何优化class UnionFind: def __init__(self, n): self.parent list(range(n)) def find(self, x): while self.parent[x] ! x: x self.parent[x] return x def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x ! root_y: self.parent[root_x] root_y def connected(self, x, y): return self.find(x) self.find(y)这个版本能跑但效率不高。如果合并顺序不好树会退化成链find操作变成O(n)。不过对于小规模数据这个版本完全够用而且代码简单不容易出错。3.2 优化版本路径压缩加按秩合并class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 return True def connected(self, x, y): return self.find(x) self.find(y)这个版本是竞赛和工程中最常用的。union返回一个布尔值表示是否发生了真正的合并这个返回值在检测环的时候非常有用。3.3 用size代替rank的版本class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False if self.size[root_x] self.size[root_y]: root_x, root_y root_y, root_x self.parent[root_y] root_x self.size[root_x] self.size[root_y] return True def get_size(self, x): return self.size[self.find(x)]用size的好处是你可以直接查询某个集合的大小这在很多题目里是刚需。比如统计连通分量的大小、判断某个集合是否超过阈值等等。rank版本做不到这一点因为rank只记录高度不记录元素个数。3.4 关键细节初始化与边界处理初始化的时候parent[i] i每个元素自成一个集合。这一步看起来简单但有一个容易忽略的点元素的编号是从0开始还是从1开始。如果题目给的节点编号是1到n你开数组的时候要开n1的大小否则会越界。另外如果元素不是连续的整数比如是字符串或者坐标点就需要先用哈希表做一个映射把每个元素映射到一个唯一的整数编号然后再用并查集。这个映射步骤在很多实际问题中是必不可少的。实操心得我在写并查集的时候习惯把find函数写成递归形式因为代码短、可读性好。但如果数据量超过10^6我会改成迭代避免递归深度过大导致栈溢出。Python的默认递归深度是1000虽然可以调但在竞赛环境中不一定能改所以大数量级下迭代更稳妥。4. 并查集的典型应用场景与实操案例4.1 检测无向图中的环这是并查集最经典的应用之一。给定一个无向图判断是否存在环。思路很简单遍历每条边如果两个端点已经在同一个集合里说明这条边连接的两个点之前已经连通了再加上这条边就形成了环。如果不在同一个集合就把它们合并。def has_cycle(n, edges): uf UnionFind(n) for u, v in edges: if not uf.union(u, v): return True return False这个逻辑非常直观。union返回False说明u和v已经在同一个集合当前这条边就是一个环的“闭合边”。4.2 统计连通分量个数初始化时每个节点自成一个集合连通分量个数为n。每成功合并一次连通分量个数减一。最后剩下的就是连通分量个数。def count_components(n, edges): uf UnionFind(n) count n for u, v in edges: if uf.union(u, v): count - 1 return count这个模式在LeetCode上有很多变体比如“省份数量”、“岛屿数量”的并查集解法等等。核心逻辑都是一样的。4.3 动态维护等价关系有些问题会不断给出“A和B是等价的”这样的条件然后要求判断某两个元素是否等价。并查集天然适合这种场景。每来一个等价条件就合并两个集合查询时直接看两个元素的根是否相同。比如有一个实际场景某系统中不断收到“用户A和用户B是同一个人”的合并请求需要随时回答“用户X和用户Y是否是同一个人”。用并查集可以在近乎O(1)的时间内完成每次合并和查询。4.4 带权并查集处理更复杂的关系基础并查集只能表示“是否在同一集合”但有些问题需要表示元素之间的具体关系比如距离、相对权重等。这时候就需要带权并查集。带权并查集在parent数组之外再加一个weight数组记录当前节点到父节点的权重。在路径压缩的时候权重要累加在合并的时候要根据题目条件计算出两个根之间的权重关系。class WeightedUnionFind: def __init__(self, n): self.parent list(range(n)) self.weight [0] * n # weight[i]表示i到parent[i]的权重 def find(self, x): if self.parent[x] ! x: root self.find(self.parent[x]) self.weight[x] self.weight[self.parent[x]] self.parent[x] root return self.parent[x] def union(self, x, y, w): # 表示x比y大w root_x self.find(x) root_y self.find(y) if root_x root_y: return self.parent[root_x] root_y self.weight[root_x] self.weight[y] w - self.weight[x]带权并查集的难点在于权重关系的推导需要根据具体题目列出等式然后解出合并时根节点之间的权重。这个推导过程容易出错建议在纸上画一画把每个变量的含义标清楚。注意带权并查集的路径压缩必须用递归因为权重累加需要从根往下传递。迭代版本写起来非常绕容易出错。如果数据量太大导致递归深度问题可以考虑用栈模拟递归但代码复杂度会上升不少。5. 常见问题与排查技巧实录5.1 并查集常见问题速查表问题现象可能原因排查方法解决方案查询结果始终为False合并时没有更新根节点检查union中是否先find再赋值确保parent[root_x] root_y而不是parent[x] y数组越界节点编号从1开始但数组从0开打印最大节点编号数组开n1大小或统一做偏移递归栈溢出数据量大且树退化成链打印递归深度改用迭代find或加按秩合并路径压缩后结果错误压缩时权重处理不当检查weight累加顺序先递归找到根再更新weight和parent合并后集合大小不对size更新遗漏检查union中size是否累加确保size[root_x] size[root_y]多组测试数据结果污染没有重新初始化检查每组数据是否新建对象每组数据重新构造UnionFind5.2 踩坑实录一个让我调了两小时的bug有一次写带权并查集题目要求维护节点之间的相对距离。我按照模板写完了样例过了但提交一直WA。调了很久才发现问题出在路径压缩的权重更新顺序上。我原来的写法是def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) self.weight[x] self.weight[self.parent[x]] return self.parent[x]看起来没问题但实际上self.parent[x]在递归返回后已经被改成了根节点而self.weight[self.parent[x]]此时是根节点的权重通常是0不是原来父节点的权重。正确的写法应该是先保存原来的父节点def find(self, x): if self.parent[x] ! x: origin_parent self.parent[x] root self.find(origin_parent) self.weight[x] self.weight[origin_parent] self.parent[x] root return self.parent[x]这个bug的隐蔽性在于对于某些数据它能跑对对于另一些数据就错了。因为路径压缩后有些节点的父节点已经是根了权重累加就变成了加0看起来“碰巧”对了。但树深一点的地方就暴露了问题。实操心得带权并查集的find函数一定要先把父节点存下来再递归再更新权重最后改父节点。顺序错了结果就错了。这个坑我踩过一次后来每次写带权并查集都会特别检查这个顺序。5.3 性能优化的几个实用技巧第一个技巧是按秩合并和路径压缩不要同时省。有些人觉得路径压缩已经够快了就不写按秩合并。单用路径压缩均摊复杂度是O(log n)虽然也不差但加上按秩合并能降到O(α(n))。代码只多几行性能提升明显没有理由不加。第二个技巧是用数组而不是字典。如果元素编号是连续的整数一定用数组不要用字典。数组的访问速度比字典快很多而且内存占用更小。只有当元素编号不连续或者不是整数时才考虑用字典或者先做映射。第三个技巧是批量查询时减少find调用。如果要对多个元素判断是否在同一集合可以先对每个元素调一次find把根存下来然后比较根是否相同。不要每次比较都重新find那样会重复走路径。第四个技巧是注意Python的递归限制。Python默认递归深度是1000如果数据量是10^5级别且树比较深递归find可能爆栈。可以在代码开头加sys.setrecursionlimit(1000000)但更稳妥的做法是直接写迭代版本。5.4 并查集 vs 其他方案的选择依据方案合并复杂度查询复杂度适用场景并查集O(α(n))O(α(n))动态连通性、等价关系DFS/BFS不支持动态合并O(VE)静态图连通性哈希表分组O(1)O(1)静态分组不支持动态合并线段树O(log n)O(log n)区间查询不支持集合合并并查集的优势在于动态性它支持在线的合并操作而且合并和查询都极快。如果问题只涉及静态的连通性判断DFS/BFS也能做但如果有大量的动态合并请求并查集是首选。6. 从刷题到工程并查集的实战经验6.1 竞赛中的并查集套路在算法竞赛中并查集经常和其他技巧结合使用。比如并查集离线处理有些问题需要按某种顺序处理查询可以先把所有操作存下来倒序处理把删除变成合并。并查集二分某些问题要求最小的阈值使得图连通可以二分答案每次用并查集判断连通性。并查集贪心比如最小生成树的Kruskal算法就是按边权排序后贪心加边用并查集判断是否成环。并查集哈希元素不是整数时先用哈希映射到整数编号。这些套路的共同点是并查集在其中扮演“维护连通性”的角色核心逻辑还是靠其他算法。并查集本身很简单难的是识别出问题可以用并查集来建模。6.2 工程中的实际应用在实际工程项目中并查集也有不少用武之地。比如社交网络好友关系判断两个用户是否属于同一个社交圈子或者合并两个圈子。图像处理中的连通区域标记把相邻的像素合并到同一个区域统计区域个数。编译器中的类型等价判断两个类型是否等价或者合并等价类型。网络管理中的设备分组根据连接关系把设备分组判断两个设备是否在同一子网。这些场景的共同特点是需要动态维护一组元素的等价关系并且频繁地查询和合并。并查集在这种场景下几乎是最优解。6.3 一个完整的实战案例岛屿数量的并查集解法题目给定一个二维网格1表示陆地0表示水。相邻的陆地上下左右属于同一个岛屿。求岛屿数量。用DFS当然可以做但用并查集也别有一番风味。思路是遍历每个格子如果是陆地就把它和右边、下边的陆地合并。最后统计有多少个集合的根是陆地。def num_islands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(rows * cols) water_count 0 for r in range(rows): for c in range(cols): if grid[r][c] 0: water_count 1 continue # 只向右和向下合并避免重复 if r 1 rows and grid[r1][c] 1: uf.union(r * cols c, (r1) * cols c) if c 1 cols and grid[r][c1] 1: uf.union(r * cols c, r * cols c 1) # 统计根节点的个数 roots set() for r in range(rows): for c in range(cols): if grid[r][c] 1: roots.add(uf.find(r * cols c)) return len(roots)这个解法的时间复杂度是O(mn * α(mn))空间复杂度是O(mn)。虽然比DFS的常数大一些但逻辑清晰而且如果后续需要动态添加陆地并查集可以直接扩展DFS就不行了。实操心得用并查集做二维网格问题时把二维坐标映射成一维编号是一个常用技巧。index r * cols c这样每个格子都有唯一的整数编号。注意cols是列数不要写成rows这个错误我见过不止一次。6.4 并查集的扩展与变体除了带权并查集还有一些其他变体值得了解可持久化并查集支持查询历史版本的连通性用可持久化数组实现复杂度O(log n)。可撤销并查集支持撤销最近的合并操作用栈记录合并历史按秩合并但不路径压缩。动态并查集支持删除边通常需要离线处理或者用更复杂的数据结构。这些变体在特定场景下有用但实现复杂度比基础并查集高不少。如果不是遇到必须用的问题基础版本加路径压缩和按秩合并已经能解决95%以上的场景。我个人在实际操作中的体会是并查集的价值不在于它有多复杂而在于它用极简的代码解决了看似复杂的问题。每次写并查集核心逻辑就那么几行但能处理连通性、等价关系、环检测、分组统计等一系列问题。这种“四两拨千斤”的感觉正是算法设计的魅力所在。最后再分享一个小技巧如果你在写并查集的时候不确定路径压缩有没有生效可以在find函数里加一个计数器统计递归调用的次数。如果压缩生效第二次查询同一个节点时递归次数应该明显减少。这个调试方法简单有效比盯着代码看半天强多了。