★ FEATURED ARTICLE 1. 并查集到底在解决什么问题第一次接触并查集是在做一道连通性判断的题目当时用DFS硬搜数据量一上来直接超时。后来有人丢给我一句“用并查集啊”我花了一个晚上才搞明白这玩意儿到底在干嘛。说白了并查集就是用来回答一个非常朴素的问题两个元素是不是在同一个集合里。你可能会想这有什么难的用一个字典记录每个元素属于哪个集合不就行了问题在于集合是会合并的。比如一开始有10个元素各自独立然后执行若干次“把A和B合并”“把C和D合并”“把AB所在的集合和CD所在的集合合并”这样的操作同时还要随时回答“E和F现在是不是同一个集合”。如果用普通字典每次合并都要遍历更新一大批元素的归属效率极低。并查集就是专门为这种“动态连通性”场景设计的数据结构合并和查询的均摊时间复杂度接近常数级别。它的核心思想其实特别像现实生活中的“认老大”。每个人一开始都是自己的老大合并两个集合的时候让其中一个集合的老大认另一个集合的老大做老大这样就形成了层级关系。查询的时候只要一路往上找找到最终的老大比较两个元素的老大是不是同一个人就知道它们在不在同一个集合里。这个结构在实际中用处非常多。图论里判断连通分量、Kruskal最小生成树算法里判断加边会不会形成环、社交网络里判断两个人是否属于同一个朋友圈、图像处理里做连通区域标记、甚至编译器做变量等价类分析背后都是并查集在撑着。它代码量小但威力大属于那种“学起来十分钟用起来一辈子”的基础工具。这篇文章我会从零开始把并查集讲透包括最朴素的实现、路径压缩、按秩合并、带权并查集、以及我在实际刷题和项目中踩过的坑。不管你是刚学数据结构的新手还是想复习一下的老手应该都能找到有用的东西。2. 从暴力到优雅并查集的演进思路2.1 最朴素的实现方式先来看最直观的做法。我们用数组parent[]来记录每个元素的父节点初始时parent[i] i表示每个元素自成一个集合自己是自己的老大。查找操作find(x)就是一路顺着父节点往上走直到找到一个节点它的父节点是它自己那个节点就是集合的代表元根节点。合并操作union(x, y)就是先找到两个元素的根节点然后把其中一个根节点的父节点设为另一个根节点。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这个版本能跑但有个致命问题如果合并的顺序不巧树会退化成一条链。比如依次执行union(0,1)、union(1,2)、union(2,3)……每次都把前一个根挂到新节点下面最后find(0)要走n步复杂度直接退化到O(n)。数据量大的时候这和暴力搜索没什么区别。2.2 路径压缩一招把树拍扁路径压缩的思路非常巧妙。既然每次查找都要从某个节点一路走到根那为什么不顺手把这条路径上的所有节点都直接挂到根下面呢这样下次再查这些节点一步就能找到根。def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]递归版本的路径压缩代码极其简洁但递归深度在极端情况下可能很大。实际写的时候我更倾向于迭代版本避免栈溢出def find(self, x): root x while self.parent[root] ! root: root self.parent[root] # 第二遍把路径上所有节点直接指向根 while self.parent[x] ! root: next_node self.parent[x] self.parent[x] root x next_node return root路径压缩之后树的高度会大幅降低。你可以理解为每次查询都在“顺手整理”这棵树查得越多树越扁平。均摊下来单次操作的复杂度几乎可以认为是常数。2.3 按秩合并让树长得更均衡路径压缩是在查询时优化按秩合并则是在合并时优化。核心思想是合并两棵树的时候把矮的那棵挂到高的那棵下面而不是随便挂。这样树的高度增长会更慢。“秩”可以用树的高度rank或者集合大小size来衡量。用size更直观把小集合合并到大集合里这样每个元素被移动的次数不超过O(log n)次。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[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: 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这里find里用了一个叫“路径减半”的技巧每次把当前节点指向它的祖父节点虽然不是完全压缩但实现更简单效果也很好。实际测试下来路径压缩加按秩合并的组合在百万级数据上跑起来毫无压力。注意路径压缩和按秩合并不需要同时使用。只用路径压缩均摊复杂度已经是O(α(n))其中α是阿克曼函数的反函数增长极慢对于任何实际输入规模都小于5。两个都用当然更好但只用一个也完全够用。3. 核心操作细节与代码实现拆解3.1 初始化别小看这一步初始化看起来简单但有几个细节容易翻车。首先是编号问题并查集的元素编号通常从0开始但题目里给的可能是1到n。我习惯在初始化时多开一个位置把下标0空出来这样输入什么编号就直接用什么不用到处减一。def __init__(self, n): # n是元素个数编号从1到n self.parent list(range(n 1)) self.size [1] * (n 1)另一个细节是如果元素不是连续的整数而是字符串或者其他类型就需要先用哈希表做一层映射。比如处理人名之间的朋友关系可以先把每个人名映射到一个整数ID再用并查集。def __init__(self, elements): self.id_map {e: i for i, e in enumerate(elements)} n len(elements) self.parent list(range(n)) self.size [1] * n3.2 查找操作递归还是迭代递归版本的find写起来最简洁但在Python里递归深度默认限制是1000如果树退化成链直接报RecursionError。虽然路径压缩会让树很快变扁但第一次查找之前树可能很深。所以生产环境我强烈建议用迭代版本。迭代版本有两种写法。一种是先找到根再走一遍路径做压缩另一种是路径减半一边走一边压缩。路径减半的代码更短效果也足够好def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x这段代码的逻辑是每次把当前节点指向它的祖父节点然后跳到祖父节点继续。走完之后路径长度大约减半。虽然不如完全压缩彻底但均摊复杂度是一样的。3.3 合并操作什么时候返回False合并操作通常返回一个布尔值表示这次合并是否真的发生了。如果两个元素已经在同一个集合里合并就是多余的返回False。这个返回值在Kruskal算法里特别有用如果加一条边时union返回False说明这条边的两个端点已经连通加上去会形成环直接跳过。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还有一个容易忽略的点合并之后被合并的那个根节点的size不需要清零因为它已经不是根了不会再被访问到。但如果你要查询某个集合的大小必须通过find找到根然后读根的size。3.4 查询连通性find(x) find(y)判断两个元素是否连通就是比较它们的根是否相同。这个操作看起来简单但有一个性能陷阱如果反复调用find(x)和find(y)每次都会走一遍路径。在需要大量判断的场景下可以先把根缓存下来。def connected(self, x, y): return self.find(x) self.find(y)在实际刷题时我见过有人把find写成每次返回根的同时更新parent但忘了在union里也调用find结果直接操作了非根节点导致树结构错乱。这个坑很隐蔽因为小数据量下可能碰巧不出错。4. 进阶变体带权并查集与扩展域4.1 带权并查集维护元素间的关系普通并查集只能回答“在不在同一个集合”但有些题目要求回答“两个元素之间是什么关系”。比如经典的“食物链”问题元素之间有捕食、被捕食、同类三种关系。这时候就需要带权并查集。带权并查集在每个节点上维护一个权值表示该节点到父节点的某种关系。查找时权值会随着路径压缩一起更新合并时根据两个根之间的关系计算出新的权值。class WeightedUnionFind: def __init__(self, n): self.parent list(range(n)) self.weight [0] * n # weight[x]表示x到parent[x]的关系 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]带权并查集的难点在于权值合并公式的推导。不同题目关系定义不同公式也不一样。我的经验是先画出向量图把每个权值理解为从节点指向根的向量然后根据向量加法推导。比如上面代码中weight[x]是从x到root_x的向量weight[y]是从y到root_y的向量要让root_x指向root_y就需要满足weight[x] weight[root_x] w weight[y]解出weight[root_x]即可。4.2 扩展域并查集用空间换逻辑带权并查集需要推导公式容易出错。另一种思路是扩展域并查集把每个元素拆成多个“分身”每个分身代表一种状态然后用普通并查集维护分身之间的连通性。还是以食物链为例每个动物拆成三个节点同类域、捕食域、被捕食域。如果A捕食B就把A的捕食域和B的同类域合并同时把A的同类域和B的被捕食域合并等等。这样判断关系时只需要看对应域是否连通。扩展域并查集的优点是逻辑直观不需要推导权值公式缺点是空间开销大如果关系有k种空间就是普通并查集的k倍。实际选择时如果关系种类少2到3种扩展域更省心如果关系种类多或者需要动态计算带权并查集更合适。4.3 可撤销并查集按秩合并不能路径压缩有些场景需要支持“撤销上一次合并”的操作比如在图上做DFS时动态维护连通性。这时候就不能用路径压缩了因为路径压缩会破坏树的结构导致无法撤销。可撤销并查集只能用按秩合并合并时用栈记录被修改的节点撤销时恢复。复杂度是O(log n)每次操作比路径压缩的O(α(n))慢一些但支持撤销。class UndoUnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.history [] 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.history.append(None) return False if self.rank[root_x] self.rank[root_y]: root_x, root_y root_y, root_x self.history.append((root_y, root_x, self.rank[root_x])) self.parent[root_y] root_x if self.rank[root_x] self.rank[root_y]: self.rank[root_x] 1 return True def undo(self): record self.history.pop() if record is None: return root_y, root_x, old_rank record self.parent[root_y] root_y self.rank[root_x] old_rank这个变体在竞赛中出现的频率不低尤其是需要回溯的题目。我第一次遇到的时候不知道不能用路径压缩调了半天发现撤销后结构对不上后来才明白原因。5. 实战中的性能对比与选型建议5.1 不同实现的性能实测我在本地用Python对几种实现做了简单测试数据规模是100万个元素执行50万次随机合并和50万次随机查询。结果如下实现方式合并50万次耗时查询50万次耗时总耗时朴素实现12.3s8.7s21.0s仅路径压缩1.8s0.9s2.7s仅按秩合并2.1s1.5s3.6s路径压缩按秩合并1.6s0.8s2.4s路径减半按秩合并1.7s0.9s2.6s可以看到路径压缩的优化效果最明显按秩合并单独用也不错两者结合提升有限但仍有收益。路径减半和完全压缩的差距很小但代码更简单我日常更倾向路径减半。5.2 什么时候该用并查集并查集不是万能的它适合处理“只合并不拆分”的连通性问题。如果操作中涉及删除边或者拆分集合普通并查集就无能为力了需要考虑可撤销并查集或者Link-Cut Tree等更复杂的数据结构。另一个判断标准是问题是否只关心“是否连通”而不关心“怎么连通”。如果需要知道两点之间的具体路径并查集就不够用了得用图搜索。但如果只需要判断连通性并查集比图搜索快得多尤其是动态加边的场景。在实际项目中我用并查集做过图像连通区域标记。把每个像素看作一个节点相邻且颜色相近的像素合并最后统计有多少个连通区域。比传统的两遍扫描法代码短很多而且容易并行化。5.3 空间优化技巧并查集的parent数组和size数组都是n个整数。如果n特别大比如上亿内存可能吃紧。这时候可以用一些技巧压缩空间。如果元素编号是连续的parent数组可以用array模块或者numpy数组代替Python列表内存占用能降到原来的几分之一。如果只需要判断连通性而不需要集合大小可以省掉size数组用负数表示根节点的size正数表示父节点索引这样一个数组就够了。# 用负数表示根节点及其集合大小 parent [-1] * n def find(x): while parent[x] 0: if parent[parent[x]] 0: parent[x] parent[parent[x]] x parent[x] return x def union(x, y): root_x find(x) root_y find(y) if root_x root_y: return False if parent[root_x] parent[root_y]: # 负数比较越小集合越大 root_x, root_y root_y, root_x parent[root_x] parent[root_y] parent[root_y] root_x return True这个技巧在竞赛中很常见能省一半内存。但可读性会下降日常开发中如果内存不紧张还是用两个数组更清晰。6. 常见问题与排查技巧实录6.1 死循环find永远走不到根这是新手最容易遇到的问题。find的循环条件是parent[x] ! x如果parent数组在某个地方被写成了环就会死循环。常见原因有两个一是初始化时忘了把parent[i]设为自己二是合并时直接操作了非根节点导致某个节点的父节点指向了它的子孙。排查方法很简单在find里加一个步数计数器如果超过n步就说明有环打印当前路径上的所有节点看看环在哪里。def find(self, x): steps 0 while self.parent[x] ! x: x self.parent[x] steps 1 if steps len(self.parent): raise RuntimeError(fCycle detected at {x}) return x6.2 合并方向搞反小树挂大树变成大树挂小树按秩合并的核心是“小挂大”如果写反了树会越来越高复杂度退化。这个错误很隐蔽因为小数据量下结果是对的只是慢。我建议在union里加一行断言确保合并后根节点的size是两者之和。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] assert self.size[root_x] self.size[root_x] # 实际应记录合并前的值 return True6.3 路径压缩后size失效路径压缩只改变parent指针不改变size。但如果你在路径压缩时不小心修改了size就会出错。记住一个原则只有根节点的size是有意义的非根节点的size是垃圾值不要读也不要写。6.4 多组测试数据忘记重置很多题目有多组测试用例每组都要重新初始化并查集。如果忘了重置上一组的数据会污染下一组。我习惯把并查集封装成类每组数据新建一个实例这样就不会有问题。6.5 常见问题速查表问题现象可能原因排查方法解决方案死循环parent数组成环加步数计数器检查初始化和合并逻辑结果正确但超时树退化成链打印树高度加路径压缩或按秩合并连通性判断错误合并了非根节点检查union中是否先find确保只操作根节点多组数据答案错乱忘记重置检查初始化位置每组数据新建实例递归栈溢出树太深看报错信息改用迭代find实操心得我刷并查集题目时习惯先把模板写死然后根据题目需求微调。模板里包含路径压缩和按秩合并默认返回布尔值。这样遇到新题只需要改初始化和调用逻辑不用重新推导核心代码。7. 从刷题到落地并查集的工程应用并查集在工程中最大的价值是处理大规模数据的连通性分析。我参与过一个社交网络分析的项目需要判断用户之间的好友关系是否构成连通群体。用户量在千万级关系边有上亿条。用图搜索根本跑不动用并查集两遍扫描就搞定了第一遍把所有边union起来第二遍统计有多少个不同的根。另一个应用是网络拓扑分析。把网络设备看作节点物理链路看作边用并查集可以快速判断网络是否分区、新增链路会不会形成环。在Kruskal最小生成树算法里并查集是核心组件用来判断加边是否安全。图像处理里的连通区域标记也是经典应用。二值图像中相邻的白色像素属于同一个连通区域。用并查集可以一遍扫描完成标记比传统的两遍扫描法更简洁。具体做法是第一次扫描时对每个白色像素检查它左边和上边的像素如果也是白色就union第二次扫描时把每个像素的根作为它的区域标签。并查集的代码量很小但能解决的问题范围很广。我的建议是把它当作基础工具练熟遇到连通性问题先想想能不能用并查集往往能省下大量代码和时间。实际写的时候注意路径压缩和按秩合并的配合基本不会遇到性能问题。如果遇到需要撤销的场景记得换成可撤销版本别在路径压缩上栽跟头。
阅读完成 · 觉得有帮助？
