1. 专题训练从“Aproblem”到掌握并查集最近在整理算法笔记翻到了以前做专题训练时标记为“Aproblem”的一系列题目。这个标记通常意味着这类题目是某个知识点的典型应用或者是我在初次接触时觉得“有点东西”的难题。而“并查集”绝对是这个列表里的常客。它不像动态规划那样变化多端也不像图论算法那样直观复杂但它在解决“连通性”和“分组”问题上有着近乎“作弊”般的简洁与高效。很多看似需要复杂模拟或者深度搜索的问题用上并查集代码量能直接砍半运行效率更是飙升。今天我就想从一个老鸟的角度拆解一下这个专题聊聊并查集到底怎么学、怎么用以及如何避开那些新手时期最容易踩的坑。并查集英文叫 Union-Find 或 Disjoint Set Union (DSU)。它的核心功能就两个合并Union和查找Find。给你一堆元素你可以把其中任意两个元素所在的集合合并成一个你也可以快速查询任意两个元素是否属于同一个集合。听起来很简单对吧但它的威力恰恰就藏在这份简单里。从社交网络的好友关系判断两个人是否间接认识到迷宫生成与求解再到编译器中的变量等价类分析甚至是一些在线游戏中的队伍系统底层都可能用到它。对于算法竞赛和面试刷题而言它更是解决“连通块计数”、“最小生成树Kruskal算法”、“最近公共祖先某些变种”等问题的基石。掌握它是迈向高阶算法学习的必经之路。2. 并查集的核心思想与数据结构设计2.1 如何用数组表示“森林”并查集最经典、最常用的实现方式是使用一个一维数组。这个数组的下标代表每一个元素通常编号从0或1开始而数组里存储的值代表这个元素的“父节点”。如果某个元素的值等于它自己的下标那它就是它所在集合的“根”Root或“代表元”。举个例子假设我们有6个元素0, 1, 2, 3, 4, 5。初始化时每个元素自成一家所以父节点就是自己。parent[] [0, 1, 2, 3, 4, 5]这表示有6棵独立的“树”每棵树只有一个节点自己就是根。现在如果我们想把元素1和元素2合并。一种常见的做法是把其中一个集合的根节点挂到另一个集合的根节点下面。比如我们把元素2的根现在是2的父节点设置为元素1的根现在是1。那么数组就变成了parent[] [0, 1, 1, 3, 4, 5] // parent[2] 1此时元素1和元素2就在同一个集合里了这个集合的根是1。如果再合并元素2和元素3呢注意我们不是直接设置parent[3] 2而是要先找到元素2和元素3各自的根。元素2的根是1元素3的根是3。然后我们把根3挂到根1下面parent[] [0, 1, 1, 1, 4, 5] // parent[3] 1这样元素1、2、3就在同一个集合里了根是1。整个结构就像一片森林每棵树代表一个集合树根就是集合的代表。注意这里的选择把谁挂到谁下面看似随意但会影响树的形状进而影响效率。我们后面会讲“按秩合并”来优化。2.2 “查找”与“合并”的朴素实现基于上面的数组我们可以写出最基础的find和union操作。查找Find给定一个元素x找到它所在集合的根。方法就是沿着父节点指针一直向上走直到找到那个父节点是自己的节点。def find(x, parent): while parent[x] ! x: # 如果不是根就继续向上找 x parent[x] return x对于上面的例子find(3, parent)的路径是3 - 1因为parent[3]1然后发现parent[1]1所以根是1。合并Union给定两个元素x和y将它们所在的集合合并。分别找到x和y的根rootX find(x),rootY find(y)。如果rootX rootY说明它们本来就在一个集合无需操作。否则将其中一个根的父亲设置为另一个根parent[rootY] rootX或parent[rootX] rootY。def union(x, y, parent): rootX find(x, parent) rootY find(y, parent) if rootX ! rootY: parent[rootY] rootX # 将rootY挂到rootX下这就是并查集最核心的逻辑。但是这个朴素版本有很大的效率问题。考虑一种最坏情况我们依次合并(0,1),(0,2),(0,3), ...最终会形成一条长长的链。此时执行find(n)操作需要遍历整条链时间复杂度退化为 O(n)。对于大量操作这是不可接受的。2.3 路径压缩让查找接近O(1)路径压缩是并查集第一个也是最重要的优化。它的思想非常巧妙既然find操作的目的是找到根那么在查找的过程中顺带把沿途所有节点的父节点都直接指向根。这样下次再查找这些节点时就能一步到位。通常我们用递归的方式实现代码简洁得惊人def find(x, parent): if parent[x] ! x: parent[x] find(parent[x], parent) # 递归查找根并赋值 return parent[x]这个过程可以这样理解find(3)发现parent[3]1它不是根于是去问find(1)。find(1)发现parent[1]1它是根于是返回1。在返回的过程中find(3)拿到了根1然后它做了一件事parent[3] 1。这样节点3的父指针就从原来的1它的直接父亲直接指向了根1。如果之前是一条长链3-2-1那么一次find(3)之后就变成了3-1和2-1假设也递归压缩了。经过多次操作后整棵树会变得非常扁平几乎所有节点都直接挂在根节点下find操作的平均时间复杂度接近常数级 O(α(n))其中 α(n) 是增长极慢的反阿克曼函数在实际应用中可视为常数。实操心得路径压缩的递归写法虽然优雅但在极端深度或某些编程语言的递归栈限制下可能有栈溢出风险。非递归写法更安全思路是先循环找到根再循环一次将路径上所有节点的父节点设为根。我通常优先使用递归因为代码清晰在算法题的数据规模下完全够用。如果担心栈深度可以换用非递归。2.4 按秩合并维持树的平衡路径压缩主要优化了“查”而“并”的操作也有优化空间。在合并两棵树时如果总是随意地将一棵树挂到另一棵树下可能会意外地产生一棵很深的树。虽然后续的find会压缩它但那个“意外”的find操作本身可能会比较耗时。“按秩合并”就是为了避免这种情况。我们引入一个额外的数组rank或size用来记录以每个节点为根的树的深度或大小的一个上界。合并时总是将秩较小的树挂到秩较大的树下。这样可以保证合并后的树深度增长较慢。如果两棵树秩相等则任意合并但需要将新根的秩加1因为深度增加了。def union(x, y, parent, rank): rootX find(x, parent) rootY find(y, parent) if rootX rootY: return # 按秩合并 if rank[rootX] rank[rootY]: parent[rootX] rootY elif rank[rootX] rank[rootY]: parent[rootY] rootX else: # 秩相等任意合并这里将rootY挂到rootX下 parent[rootY] rootX rank[rootX] 1 # 合并后深度增加了这里的“秩”并不严格等于树的深度因为路径压缩会改变深度但它是一个有效的启发式值能很好地指导合并顺序。路径压缩和按秩合并一起使用可以将并查集单次操作的平均时间复杂度优化到近乎常数这是它高效的关键。注意事项在同时使用路径压缩和按秩合并时rank数组的含义更接近于“秩的一个上界”而不是精确的深度。因此在路径压缩后我们通常不会去更新其他节点的rank值。这个“不更新”是正确的不会影响算法的正确性和渐进复杂度。这是很多初学者容易困惑的地方记住一点rank主要用在union时做决策find操作不用管它。3. 并查集的经典应用场景与解题模板3.1 连通性问题与岛屿数量这是并查集最直白的应用。LeetCode 上的“岛屿数量”Number of Islands问题虽然通常用DFS/BFS解决但用并查集也别有一番风味。题目给定一个二维网格1代表陆地0代表水计算岛屿的数量相连的陆地视为一个岛屿。思路初始化并查集大小为网格中单元格的总数。每个1的单元格初始时都是一个独立的“岛屿”。遍历整个网格。对于每个1的单元格查看其右侧和下方的邻居避免重复连接。如果邻居也是1则将当前单元格与邻居单元格在并查集中进行union操作。遍历结束后统计有多少个1的单元格其父节点仍然是它自己即根节点这个数量就是岛屿的数量。这里的关键技巧是二维坐标到一维索引的映射index i * n j其中n是列数。这样就能用一维的并查集来处理二维的连通关系。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.count n # 初始集合数这里指‘1’的个数后续会动态减 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): rootX self.find(x) rootY self.find(y) if rootX ! rootY: self.parent[rootY] rootX self.count - 1 # 每成功合并一次集合岛屿数减1 def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(rows * cols) # 首先统计所有‘1’的位置并初始化“虚拟”的集合 # 更常见的做法是只对‘1’进行合并最后统计根节点数。 # 这里采用另一种思路初始化时count为0遇到‘1’先加1合并时减1。 # 但为了清晰我们采用最后统计根节点的方法。 # 初始化将所有‘1’视为独立集合但并查集大小仍是rows*cols‘0’也占位置。 # 优化只处理‘1’‘0’不参与。我们修改一下UnionFind让它支持动态处理。 # 实际上更简单的模板是 dummy_node rows * cols # 一个虚拟节点代表“水” uf UnionFind(rows * cols 1) # 多一个位置给虚拟节点 for i in range(rows): for j in range(cols): if grid[i][j] 1: # 与右方、下方合并 if i 1 rows and grid[i1][j] 1: uf.union(i*cols j, (i1)*cols j) if j 1 cols and grid[i][j1] 1: uf.union(i*cols j, i*cols (j1)) else: # 如果是水就把它和虚拟节点合并 uf.union(i*cols j, dummy_node) # 统计岛屿数量所有‘1’的格子中根节点不是虚拟节点的唯一根的数量 root_set set() for i in range(rows): for j in range(cols): if grid[i][j] 1: root uf.find(i*cols j) if root ! uf.find(dummy_node): # 根不是水 root_set.add(root) return len(root_set)这个例子展示了并查集在网格连通性问题上的应用。相比DFS/BFS并查集的代码逻辑更集中主要就是union并且可以动态处理网格变化比如后续有单元格从0变成1而无需重新全局搜索。3.2 关系传递与等式方程的可满足性LeetCode 990 “等式方程的可满足性” 是并查集处理关系传递性的经典题。给定一个字符串数组equations包含ab或a!b的等式/不等式判断所有方程是否可能同时成立。思路遍历所有等式()将等式两边的变量进行union操作。这相当于声明这些变量是相等的属于同一个集合。遍历所有不等式(!)检查不等式两边的变量。如果它们属于同一个集合即find(a) find(b)那就矛盾了因为等式告诉我们它们相等而不等式要求它们不等。如果发现矛盾返回false。如果所有不等式检查都通过返回true。这里并查集完美地维护了“等价关系”的传递性。ab和bc能推导出ac这个推导过程由并查集的union和find自动完成。class UnionFind: # ... 同上实现find和union ... def equationsPossible(equations): uf UnionFind(26) # 26个小写字母 # 第一遍处理所有等式 for eq in equations: if eq[1] : x ord(eq[0]) - ord(a) y ord(eq[3]) - ord(a) uf.union(x, y) # 第二遍检查所有不等式 for eq in equations: if eq[1] !: x ord(eq[0]) - ord(a) y ord(eq[3]) - ord(a) if uf.find(x) uf.find(y): return False return True这个模板非常清晰先union所有确定的关系再用find检查冲突。它适用于所有需要维护元素分组并后续进行冲突检测的场景。3.3 带权并查集维护相对关系前面两个例子中并查集只维护了“是否属于同一组”的信息。但有些问题需要知道组内元素的相对关系。比如经典的“食物链”问题或者判断一句话里的人物关系是否矛盾。这就需要带权并查集。我们在每个节点到其父节点的边上增加一个“权值”这个权值代表该节点与其父节点的某种关系如差值、比例、类别等。在find进行路径压缩时需要同时更新权值在union合并时需要根据两个元素与各自根的关系推导出两个根之间的关系并设置正确的权值。以“判断数组是否可以通过交换特定位置元素变得有序”的变种题为例假设我们有一些数对(i, j)表示位置i和j的数可以任意交换。问是否可以通过这些交换让数组有序。我们可以把可以交换的位置看成是连通的它们形成一个集合集合内的数字可以自由排列。那么要使数组最终有序每个集合里必须包含且仅包含那些“最终应该在这个集合位置上的数字”。一个更简单的模型是给定一些(a, b)对表示a和b必须属于同一集合。问能否将所有人分成两个集合满足某些条件。带权并查集通常用“关系”的模运算来表示。例如在“食物链”问题中关系有三种A吃BB吃CC吃A形成一个循环。我们可以定义权值0表示同类1表示被父节点吃2表示吃父节点模3运算。find时权值要累加取模union时要根据已知的两个节点与各自根的关系以及两个节点之间的关系解出两个根之间应有的关系。由于带权并查集代码较长且问题特定这里不展开完整代码但它的核心模板如下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: origin_parent self.parent[x] self.parent[x] self.find(self.parent[x]) # 路径压缩时更新权值x与新根的关系 (x与旧根的关系 旧根与新根的关系) % MOD self.weight[x] (self.weight[x] self.weight[origin_parent]) % MOD return self.parent[x] def union(self, x, y, relation): # relation 表示 x 与 y 的关系 rootX, rootY self.find(x), self.find(y) if rootX rootY: # 检查已有关系是否矛盾 # (weight[x] - weight[y]) % MOD 应该等于 relation return (self.weight[x] - self.weight[y]) % MOD relation # 合并需要计算 rootX 与 rootY 的关系 # 有公式relation(x, y) weight[x] - weight[y] relation(rootX, rootY) # 所以 relation(rootX, rootY) relation(x, y) weight[y] - weight[x] rel_root (relation self.weight[y] - self.weight[x]) % MOD self.parent[rootY] rootX self.weight[rootY] rel_root return True理解带权并查集的关键在于画出关系链推导出权值更新的公式。这是并查集专题里难度较高的部分但一旦掌握解决复杂关系问题就得心应手。4. 实战刷题策略与高效调试技巧4.1 如何识别并查集问题并不是所有连通性问题都用并查集最好。我总结了几条特征当题目出现这些特征时可以优先考虑并查集动态连通性问题涉及大量“将两个元素连接起来”和“查询两个元素是否连通”的操作。如果只是单次查询BFS/DFS可能更直接但如果是多次、交替的合并与查询并查集的优势就大了。分组与等价关系需要将元素分成若干组同组内的元素满足某种等价、互通、或者必须在一起的性质。典型的如“朋友的朋友是朋友”、“等式传递”、“可以交换的位置”。离线查询有时问题会给出一系列操作和查询我们可以先读完所有输入然后按照特定顺序处理比如先处理所有合并操作再处理查询。并查集很适合这种模式。作为其他算法的子过程最典型的就是Kruskal最小生成树算法。需要对边按权重排序后依次尝试加入用并查集来判断加入这条边是否会形成环即边的两个端点是否已经连通。一个简单的判断方法是如果题目描述里频繁出现“连接”、“合并”、“是否属于同一组”、“关系是否矛盾”这些关键词就该亮出并查集这把“瑞士军刀”了。4.2 通用模板与初始化陷阱经过大量练习我固定了一套自己的并查集模板它包含了路径压缩和按秩合并并且把parent和rank数组作为实例变量用起来很顺手class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [1] * n # 初始秩为1代表树的大小或深度 # 有时需要 count 记录集合数初始为 n # self.count 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): rootX self.find(x) rootY self.find(y) if rootX rootY: return False # 未合并 # 按秩合并 if self.rank[rootX] self.rank[rootY]: rootX, rootY rootY, rootX # 交换确保rootX是秩大的根 self.parent[rootY] rootX if self.rank[rootX] self.rank[rootY]: self.rank[rootX] 1 # self.count - 1 return True # 成功合并初始化陷阱最常犯的错误就是初始化不对。parent数组一定要初始化为parent[i] i这是并查集一切逻辑的起点。我有一次调试了半小时就是因为写成了parent [0] * n。另外rank数组的初始值可以是0也可以是1这取决于你把rank定义为高度还是大小。按高度合并通常初始为0按大小合并初始为1。只要合并逻辑一致就行。我的模板里用rank代表一个近似高度初始为1这样在秩相等时合并高度会加1逻辑比较自然。4.3 调试与常见错误排查即使有了模板调试并查集的问题有时也挺让人头疼。问题往往不直接出在union和find上而是出在如何将原问题映射到并查集操作。常见错误1索引映射错误尤其是在处理二维网格时把(i, j)映射到一维索引idx i * cols j一定要确保cols是列数而不是行数。我曾经因为把rows和cols搞反导致合并了完全不相干的格子结果怎么算都不对。排查方法打印出小规模测试用例的网格和对应的并查集parent数组。手动模拟一下合并过程看看union操作对应的索引是否正确。常见错误2合并条件遗漏或重复比如在岛屿问题中我们只向右和向下合并以避免重复。如果向四个方向合并必须确保每个连接只被处理一次否则虽然结果可能正确但会做大量重复的find操作。更隐蔽的错误是在某些问题中合并的条件不是简单的相邻而是满足某个公式或规则漏掉一个条件就会导致连通块计算错误。排查方法画图在纸上画出元素和它们之间的关系明确哪些应该被合并。然后单步调试你的代码或者打印出每次union操作的两个元素检查是否符合预期。常见错误3带权并查集关系推导错误这是最难调试的。权值更新公式写错一个符号或者模数用错都会导致结果全盘皆输。排查方法小数据暴力对拍写一个暴力算法比如BFS判断关系用于小数据量n10的随机测试。生成大量随机数据和操作对比并查集的结果和暴力结果是否一致。这是最有效的查错方法。打印关系链在find和union函数中加入详细的打印语句输出当前节点的权值、父节点权值、计算出的新权值等。对照你推导的公式一步步检查。理解模运算确保你对模运算的性质如(a-b) mod M可能为负在编程中要转为正数非常熟悉。在Python中(a-b) % M会自动得到非负结果但在其他语言如C/Java中%可能是取余运算对于负数结果需要手动调整。一个实用的调试技巧可视化并查集状态对于不超过20个节点的问题可以写一个简单的函数来打印并查集的状态def debug_dsu(dsu, n): print(Index:, list(range(n))) print(Parent:, dsu.parent) print(Roots:, [dsu.find(i) for i in range(n)]) # 打印每个集合的成员 from collections import defaultdict groups defaultdict(list) for i in range(n): groups[dsu.find(i)].append(i) print(Groups:, dict(groups))在关键操作后调用这个函数可以一目了然地看到合并的效果非常有助于定位问题。5. 从“Aproblem”到举一反三并查集的变种与拓展刷完基础题你会遇到很多“Aproblem”级别的变种题。它们都在基础并查集上套了一层“外壳”核心依然是union和find。变种1维护集合大小或集合数量我们经常需要知道某个集合有多少个元素或者总共有多少个集合。这很简单在初始化时用一个size数组size[i]1。在union时将小集合的根挂到大集合的根下并更新大集合的sizesize[rootX] size[rootY]。集合数量count可以在每次成功union后减1。变种2支持“断开连接”标准的并查集只支持合并不支持拆分。但有些问题需要。一种思路是使用“离线处理逆向操作”如果所有操作已知我们可以从最终状态倒着往回推把“断开”操作变成逆向的“合并”操作。另一种思路是使用“时光倒流”或“持久化并查集”但这已经属于高级技巧了。变种3二维并查集与动态添加比如在游戏地图中动态地添加障碍物或打通通道实时查询两个区域是否连通。这需要并查集支持“删除”操作将某个元素从集合中移除通常比较棘手。更常见的做法是将问题转化为对静态结构的多重查询或者使用其他数据结构如线段树维护连通性。举一反三的练习路径基础LeetCode 547 (省份数量)、LeetCode 200 (岛屿数量)、LeetCode 684 (冗余连接)、LeetCode 721 (账户合并)。进阶LeetCode 399 (除法求值 - 带权并查集)、LeetCode 765 (情侣牵手 - 巧妙建模)、LeetCode 128 (最长连续序列 - 并查集并非最优但可做)。挑战LeetCode 803 (打砖块 - 逆向并查集)、LeetCode 952 (按公因数计算最大组件大小 - 并查集数论)。并查集的魅力在于你理解它的核心后面对各种复杂问题都能尝试着去建模哪些元素是点怎样的关系需要建边union要查询的信息是否可以通过find操作间接得到多思考这几个问题并查集就从一道题目的解法变成你解决问题工具箱里一件趁手的兵器了。最后分享一个我自己的体会学习并查集初期死记模板没问题但一定要亲手实现几次并尝试用不同的方式比如不用递归实现路径压缩。然后去找3-5道不同应用场景的题目反复练习直到你能在几分钟内写出无bug的代码并且能清晰地向别人解释为什么这么做。这时你才算真正“拿下”了这个专题以后再看到“Aproblem”里出现它心里就有底了。