1. 从“找老大”到“抱大腿”并查集到底在解决什么问题如果你写过一些需要处理“分组”或者“连通性”问题的代码比如社交网络的好友关系、游戏中的玩家组队、或者图像处理中的像素连通区域标记那你大概率会遇到一个让人头疼的场景如何高效地判断两个元素是否属于同一个集合以及如何将两个集合合并最朴素的想法可能是用数组或者列表来维护每个元素所属的集合编号查询是O(1)的但合并时却需要遍历其中一个集合的所有元素来修改编号这在数据量大、合并操作频繁时效率会急剧下降。这时候一个听起来有点抽象但用起来极其巧妙的数据结构就该登场了——并查集。并查集英文叫Union-Find或者Disjoint-Set。它的核心任务就是维护一堆不相交的集合并支持两种操作查找某个元素属于哪个集合Find以及合并两个集合Union。它不关心集合里具体有什么元素只关心“谁和谁是一伙的”这个关系。你可以把它想象成一个江湖门派管理系统一开始每个人都是自成一派单元素集合通过“合并”操作小门派可以并入大门派通过“查找”操作你可以快速知道任意两个人的“总舵主”是不是同一个人从而判断他们是否同属一个门派。我第一次在工程中真正用上并查集是在处理一个网络设备拓扑发现的场景。我们需要从海量的链路数据中快速归并出一个个独立的子网。每条链路信息就像告诉你两个设备是直接相连的。用并查集初始化时每个设备自己就是一个集合。每读到一条链路就尝试合并链路两端设备所在的集合。处理完所有链路后拥有相同“代表”的设备就自然被划分到了同一个子网里。整个过程清晰、高效代码写起来也异常简洁那种“四两拨千斤”的感觉让我对这个数据结构印象深刻。那么并查集是如何做到高效查询和合并的呢它的秘诀不在于存储完整的集合信息而在于为每个集合选出一个“代表元”并通过一种巧妙的树形结构让每个元素都能快速找到自己所在集合的代表。接下来我们就深入它的内部看看这棵“树”是怎么长成的。2. 并查集的核心三要素数组、查找与路径压缩并查集的实现通常非常简洁其核心往往就是一个一维数组。这个数组的下标代表元素本身而数组里存储的值则代表这个元素的“父节点”。如果某个元素的值就是它自己即parent[i] i那么恭喜它就是当前这个集合的“根节点”或者说“代表元”。2.1 初始化各自为政一开始每个元素都是一个独立的集合自己是自己的父节点。用代码表示初始化就是遍历一遍所有元素def __init__(self, n): self.parent [i for i in range(n)] # 初始时每个元素的父节点都是自己 # 可选记录每个集合的秩rank或大小size用于优化合并 self.rank [0] * n这里的n是元素的总数。parent数组是并查集的状态存储核心。rank数组是一个优化手段我们稍后会详细解释。2.2 查找操作顺藤摸瓜找祖宗查找操作find(x)的目标是找到元素x所在集合的根节点。最直接的方法就是沿着父指针一路向上找直到找到那个父节点是自己的节点。def find_simple(self, x): while self.parent[x] ! x: x self.parent[x] return x这个方法在树比较深的时候效率会变低。想象一下如果我们的合并操作总是把一棵树挂到另一棵树的叶子节点下那么树可能会退化成一条长长的链这时find操作的时间复杂度就变成了 O(n)。2.3 路径压缩让树变扁平的神来之笔为了解决退化链的问题并查集最经典的优化之一——路径压缩就出现了。它的思想非常直观既然我这次费劲找到了根那我为什么不顺便把沿途所有人的父节点都直接改成根呢这样下次查找他们任何一个人时都只需要一步。通常我们使用递归来实现代码简洁得惊人def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 递归查找并压缩 return self.parent[x]这个过程可以理解为“认祖归宗”的同时让沿途所有人都“拜了把子”直接认根为父。经过路径压缩后树的深度会变得非常小理想情况下可以接近常数。这也是并查集查询操作均摊时间复杂度能达到近乎 O(1) 的关键。注意路径压缩在递归实现时对于极深的数据可能会有栈溢出的风险。在实际生产环境的某些语言或场景下可能会采用迭代的写法来避免这个问题。迭代写法的核心是用一个循环先找到根再用一个循环将路径上所有节点的父节点指向根。2.4 合并操作不是简单的牵手合并操作union(x, y)的目标是将元素x和元素y所在的集合合并。最朴素的想法是直接把一个集合的根节点的父指针指向另一个集合的根节点。def union_simple(self, x, y): root_x self.find(x) root_y self.find(y) if root_x ! root_y: self.parent[root_x] root_y # 将x的根挂到y的根下但是这样随意地挂接很可能又会导致树变高。比如总是把大树挂到小树下树的高度就会不受控制地增长。3. 按秩合并如何优雅地“抱大腿”为了在合并时也能控制树的高度我们需要一个策略来决定“谁挂到谁下面”。这就是按秩合并。这里的“秩”可以理解为树的高度的一个上界或者集合的大小。我们维护一个额外的rank数组。初始化时每个集合的秩为0或大小为1。合并时我们总是将秩较小的树的根连接到秩较大的树的根上。如果两棵树秩相等则任意连接但被连接的那棵树的秩需要加1因为高度可能增加了。def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return # 已经在同一集合无需合并 # 按秩合并 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: # 秩相等任意连接但被连接的根秩1 self.parent[root_y] root_x self.rank[root_x] 1为什么按秩合并有效它的核心目的是避免树的不必要增高。将矮树挂到高树上合并后的树高度不变矮树的高度被高树“吸收”了。只有当两棵树高度相同时合并后整体高度才会增加1。这个策略与路径压缩配合可以保证并查集的操作效率极高。实操心得在绝大多数情况下同时使用“路径压缩”和“按秩合并”并查集的每个操作的平均时间复杂度可以看作是阿克曼函数的反函数这是一个增长极其缓慢的函数对于任何在宇宙可观测范围内的实际数据规模这个值都不会超过5。因此在算法分析中我们通常认为并查集的操作是近乎常数时间O(α(n)) 的。这是它强大威力的数学基础。4. 从理论到实战并查集的经典问题与变种理解了基本原理我们来看看并查集能解决哪些具体问题。我会通过几个例子展示如何将实际问题抽象成并查集模型。4.1 朋友圈问题这是最经典的并查集应用题。问题描述假设有n个人给出m对朋友关系朋友关系具有传递性。请问最终有多少个朋友圈抽象每个人是一个元素。每给出一对朋友关系(a, b)就执行一次union(a, b)。处理完所有关系后统计有多少个不同的根节点即parent[i] i的i的个数就是朋友圈的数量。代码框架def findCircleNum(isConnected): n len(isConnected) uf UnionFind(n) for i in range(n): for j in range(i1, n): # 矩阵是对称的遍历一半即可 if isConnected[i][j] 1: uf.union(i, j) # 统计根的数量 return sum(1 for i in range(n) if uf.find(i) i)4.2 岛屿数量问题网格版给定一个由1陆地和0水组成的二维网格计算网格中岛屿的数量。岛屿由水平或垂直方向上相邻的陆地连接形成。抽象我们可以将每个陆地格子看作一个元素。初始化时每个1的格子自成一个集合。然后遍历网格对于每个陆地格子查看其右方和下方的邻居避免重复合并如果邻居也是陆地则进行union操作。最终岛屿的数量就是不同集合的数量。为什么只看右和下因为遍历是从左到右、从上到下的。当处理到格子(i, j)时它的左邻居(i, j-1)和上邻居(i-1, j)已经被处理过了。如果(i, j)与它们连通那么在处理左、上邻居时合并操作已经执行。所以我们只需要合并当前格子与右、下邻居就能覆盖所有连通情况且不会重复合并。代码关键点def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(rows * cols) # 将二维坐标映射到一维 count sum(1 for i in range(rows) for j in range(cols) if grid[i][j] 1) # 初始陆地数 for i in range(rows): for j in range(cols): if grid[i][j] 1: idx i * cols j # 检查右邻居 if j 1 cols and grid[i][j1] 1: if uf.union(idx, i * cols (j1)): count - 1 # 合并一次岛屿数量减1 # 检查下邻居 if i 1 rows and grid[i1][j] 1: if uf.union(idx, (i1) * cols j): count - 1 return count这里union函数可以返回一个布尔值指示是否执行了实际的合并操作。每合并一次意味着两个原本分离的陆地连成了一片所以岛屿总数减1。这种方法可以在遍历过程中动态计算数量无需最后再统计根节点。4.3 带权并查集并查集不仅能维护“是否连通”的关系还能维护节点之间的某种“差值”关系。这类问题通常被称为“带权并查集”或“扩展并查集”。一个经典例子是“食物链”问题。动物分为A、B、C三类A吃BB吃CC吃A。给出两种陈述1) X和Y是同类2) X吃Y。这些陈述可能真假混杂问有多少句假话。抽象我们不仅需要知道动物属于哪个集合还需要知道集合内动物之间的“关系”。我们可以让每个节点维护一个到根节点的“权值”这个权值模3的结果可以表示它与根节点的关系0同类1被根吃2吃根。查找在路径压缩时需要同时更新权值。合并根据给定的关系同类或捕食推导出两个根节点之间应有的权值差然后进行合并。这需要对并查集的find和union操作进行扩展使其在维护父指针的同时维护一个额外的权重数组。代码逻辑会复杂一些但核心思想依然是并查集。踩坑实录实现带权并查集时最易错的地方是权值更新的方向。在find中进行路径压缩时权值的更新是从当前节点累加到根节点。在union时计算两个根节点之间的新权值关系一定要画图推导清楚向量关系否则很容易把正负号弄反。我的经验是定义清楚权值的物理意义如weight[x]表示x与parent[x]的关系然后所有推导都基于这个定义进行。5. 并查集在工程中的实战技巧与避坑指南在实际项目中使用并查集远不止套用模板那么简单。下面分享几个我踩过坑才总结出来的经验。5.1 初始化大小的选择并查集初始化时需要知道元素的总数n。这个n应该是所有可能出现的、需要被纳入考虑的唯一元素的个数。场景一元素ID连续。比如处理0到N-1的节点直接n N。场景二元素ID不连续但范围已知。比如节点ID在[0, 10^5]之间跳跃出现但最大ID已知。这时n应设为max_id 1。虽然会浪费一些空间但数组访问是O(1)效率高。场景三元素ID未知或范围极大。比如节点是字符串或自定义对象。这时就不能直接用数组了需要结合哈希表。用哈希表将元素映射到一个从0开始的连续索引再用这个索引作为并查集数组的下标。这增加了O(1)的哈希开销但灵活性大大增强。class UnionFindWithMap: def __init__(self): self.parent {} self.rank {} def find(self, x): # 如果x还没出现过则初始化 if x not in self.parent: self.parent[x] x self.rank[x] 0 return x # ... 标准的带路径压缩的find if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # ... 标准的按秩合并5.2 并查集无法“拆散”这是并查集一个重要的局限性它只支持合并Union和查找Find不支持分割Split。一旦两个集合被合并就无法再将它们分开除非重置整个数据结构。这意味着如果你的应用场景中元素之间的关系是动态可解除的比如社交网络中的解除好友关系那么单纯的并查集就不适用了。你可能需要考虑其他数据结构如动态图连通性算法或者使用离线处理技巧将所有操作读入后从后往前处理将“删除边”转化为“添加边”。5.3 统计集合信息有时我们不仅需要知道是否连通还需要知道每个集合的大小、元素列表等。我们可以在并查集中额外维护一个size数组。初始化size[i] 1。合并时将小集合的根挂到大集合的根下后更新大集合的sizesize[root_big] size[root_small]。注意size信息只维护在根节点上是准确且高效的。在路径压缩后非根节点的size值不再代表其所在集合的大小。因此查询集合大小时必须先find到根节点然后访问根的size。5.4 性能调优与测试虽然并查集的均摊复杂度极优但在极端情况下例如进行数百万次操作实现细节的微小差异也会带来可观的性能区别。递归 vs 迭代路径压缩的递归写法简洁但存在函数调用开销和栈溢出风险。在性能要求苛刻或递归深度可能很大的场景使用迭代写法是更安全的选择。“按秩合并”中“秩”的含义使用树高rank还是集合大小size作为合并依据理论上按树高合并能更严格地控制树高。但按大小合并实现起来一样简单且有时能直接提供集合大小信息。在实际中两者性能差异微乎其微选择你需要的那个即可。输入数据的随机性如果合并操作总是以某种不利顺序进行比如总是合并两个大小相似的集合可能会比随机顺序带来稍多的操作次数。但对于均摊复杂度来说这影响不大。一个实用的建议是在编写关键路径的代码时可以为并查集实现提供一个简单的性能计数器在find和union中统计递归深度或循环次数在开发阶段帮助你了解数据结构的实际运行情况。并查集是一个“想法简单效果卓越”的典范。它用最少的空间一个数组和巧妙的优化路径压缩、按秩合并解决了看似需要复杂维护的集合关系问题。下次当你遇到需要处理动态连通性的场景时不妨先想一想这个问题能不能用并查集来优雅地解决很多时候答案都是肯定的。
