1. 并查集到底在解决什么问题第一次接触并查集很多人会被这个名字吓到。“并”是合并“查”是查询“集”是集合三个字拆开看其实已经把它的全部功能说完了把两个集合合并成一个查询某个元素属于哪个集合。就这么简单。但就是这么简单的三个操作在算法面试和实际工程里的出场率高得离谱。我做过一个粗略统计在近几年的笔试真题里并查集相关的题目出现频率稳定在前十。为什么因为它解决了一类非常本质的问题动态连通性。什么叫动态连通性你可以想象一个社交网络用户之间不断加好友你需要随时回答“用户A和用户B是否在同一个朋友圈里”。注意这个“朋友圈”不是直接好友关系而是通过一连串好友关系间接连通的。A认识BB认识C那A和C就在同一个圈子里。随着加好友的操作不断发生圈子会不断合并你需要动态地、快速地给出答案。用图论的话说就是在一个不断加边的无向图中判断任意两个点是否连通。你当然可以用BFS或DFS每次重新搜一遍但每次查询的代价是O(VE)如果有大量查询性能会崩掉。并查集就是专门为这种场景设计的它能让合并和查询的均摊时间复杂度降到几乎常数级别——具体来说是O(α(n))其中α是阿克曼函数的反函数对于任何你能想象到的nα(n)都不会超过5。换句话说你可以认为它就是O(1)。我第一次真正理解并查集的价值是在做一个图像处理的小项目时。当时需要把相邻的相似像素合并成区域用BFS每次重新遍历效率太低换成并查集之后整个处理速度提升了一个数量级。从那以后我就养成了一个习惯只要看到“连通”“分组”“合并”“是否属于同一类”这些关键词第一反应就是并查集。这篇文章我会从最基础的结构讲起把路径压缩和按秩合并这两个核心优化讲透然后给出一个可以直接套用的模板最后用几道经典例题带你走一遍完整的解题思路。不管你是刚学数据结构的新手还是想复习一下准备面试的老手应该都能从中找到有用的东西。2. 并查集的核心原理与设计思路2.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这个版本能跑但有一个致命问题如果合并的顺序不巧树会退化成一条链。比如依次执行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 按秩合并让矮树挂到高树下路径压缩解决的是“查找”的效率问题而按秩合并解决的是“合并”的策略问题。如果每次合并都随便挂可能会把一棵很高的树挂到一棵很矮的树下面导致新树的高度增加后续查找变慢。按秩合并的原则是总是把矮的树挂到高的树下面。这里的“秩”可以理解为树的高度或者节点数量的近似。如果两棵树高度不同矮的挂到高的下面新树的高度不变如果高度相同随便挂一个新树高度加一。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 秩初始为0 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 # 按秩合并矮树挂到高树下 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这里有一个常见的误区很多人以为用了路径压缩之后rank就不再准确反映树的高度了。确实路径压缩会改变树的高度但rank并不需要精确等于当前高度它只是一个合并时的参考依据。即使rank不准确按秩合并仍然能保证树的高度在O(log n)级别。所以两者可以安全地一起使用。2.4 两种优化到底该不该同时用理论上路径压缩和按秩合并一起用复杂度是O(α(n))这是理论最优。但在实际刷题和工程中我个人的经验是只用路径压缩通常就够了。原因很简单。路径压缩的均摊复杂度已经是O(α(n))级别单独使用时是O(log n)均摊但实际运行中非常接近常数而按秩合并需要额外维护一个rank数组增加了代码复杂度和内存开销。在绝大多数题目中数据规模不会大到需要两者同时优化的程度。不过有一种情况例外如果你需要可持久化并查集也就是保留历史版本那就不能用路径压缩因为路径压缩会修改历史结构只能用按秩合并。这是另一个话题这里不展开。我的建议是日常刷题和面试写路径压缩就够了代码简洁不容易出错。如果题目数据量特别大或者你对性能有极致要求再加上按秩合并。3. 并查集的完整实现与实操要点3.1 一份可以直接抄的模板下面这份模板是我用了很多年的版本兼顾了简洁性和性能。你可以直接复制到你的代码里用。class UnionFind: def __init__(self, n): 初始化n个元素的并查集编号0到n-1 self.parent list(range(n)) self.rank [0] * n self.count n # 连通分量个数 def find(self, x): 查找x的根节点带路径压缩迭代版 root x while self.parent[root] ! root: root self.parent[root] # 路径压缩 while self.parent[x] ! root: self.parent[x], x root, self.parent[x] return root def union(self, x, y): 合并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]: root_x, root_y root_y, root_x self.parent[root_y] root_x if self.rank[root_x] self.rank[root_y]: self.rank[root_x] 1 self.count - 1 return True def connected(self, x, y): 判断x和y是否连通 return self.find(x) self.find(y) def get_count(self): 返回当前连通分量个数 return self.count这份模板有几个设计细节值得说明count变量维护连通分量个数很多题目需要这个信息省得每次重新统计。union返回布尔值表示是否真的发生了合并。如果两个元素本来就在同一个集合返回False。这个返回值在某些题目里很有用比如判断加边是否形成环。find用迭代写法避免递归深度问题。路径压缩的写法用了Python的元组赋值一行搞定但可读性稍差。如果你觉得不好理解可以拆成三行。3.2 初始化时的常见坑初始化看起来简单但有几个坑我踩过。第一个坑是编号从0还是从1开始。有些题目元素编号从1开始如果你直接开n大小的数组访问n就会越界。解决办法是要么开n1大小要么在传入前统一减一。我个人的习惯是统一转成0-based在读取输入的时候减一这样内部逻辑不用特殊处理。第二个坑是元素不是连续整数。比如元素是字符串或者大整数不能直接作为数组下标。这时候需要用哈希表做映射把每个元素映射到一个连续的整数编号。或者直接用字典实现并查集class UnionFindDict: def __init__(self): self.parent {} def find(self, x): if x not in self.parent: self.parent[x] x return x # 路径压缩 root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: self.parent[x], x root, self.parent[x] return root 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字典版本的好处是不需要预先知道元素范围动态添加即可。缺点是常数比数组版本大而且没有按秩合并。对于元素种类不确定的题目字典版本很实用。第三个坑是多组测试数据的重置。如果题目有多组测试用例每次都要重新初始化并查集。千万不要忘了重置否则上一组的数据会污染下一组。我一般把并查集封装成类每组数据new一个对象这样最不容易出错。3.3 路径压缩的两种写法对比路径压缩有递归和迭代两种写法我前面都给了。这里再详细对比一下。递归写法代码短逻辑清晰但有两个问题一是递归深度受限于树的高度虽然路径压缩后树很矮但在压缩之前如果树退化成链递归可能爆栈二是函数调用有开销在Python这种语言里递归性能不如迭代。迭代写法代码长一些但没有栈溢出风险性能也更好。我实测过在10万次操作的规模下迭代版本比递归版本快大约20%到30%。所以如果你追求性能用迭代版本。不过有一种情况递归写法更方便带权并查集。带权并查集需要在查找过程中累加路径上的权值递归写法处理起来更自然。这个后面会讲到。3.4 并查集的复杂度到底怎么算很多人只知道并查集“很快”但说不清楚到底多快。这里我尽量用通俗的方式解释一下。只用路径压缩不用按秩合并时单次操作的均摊复杂度是O(log n)。注意是均摊不是每次都是O(log n)。有些操作可能很快有些稍慢但平均下来是O(log n)。同时用路径压缩和按秩合并时单次操作的均摊复杂度是O(α(n))。α是阿克曼函数的反函数增长极其缓慢。对于n等于宇宙中原子总数约10^80的情况α(n)也不超过4。所以你可以认为它是常数。实际测试中对于100万个元素、100万次操作并查集的总耗时通常在几百毫秒级别。这个性能对于绝大多数应用场景都绰绰有余。实操心得如果你在面试中被问到并查集的复杂度回答O(α(n))并解释α的含义基本就能让面试官满意。如果能进一步说明“实际可视为O(1)”效果更好。4. 经典例题实战拆解4.1 朋友圈问题并查集最直接的应用这是并查集最经典的入门题。题目描述是有n个人编号1到n。给出m对好友关系好友关系具有传递性。问有多少个朋友圈。这道题就是并查集的直译。每个人初始是一个独立的集合每读入一对好友关系就合并两个集合最后统计有多少个不同的根节点。def find_circle_num(n, relationships): uf UnionFind(n) for a, b in relationships: uf.union(a - 1, b - 1) # 转成0-based return uf.get_count()这道题的关键点在于理解“好友关系具有传递性”这句话。A和B是好友B和C是好友那么A和C也在同一个朋友圈。这正是并查集合并操作要解决的问题。我见过一些初学者试图用BFS来做这道题每次从一个未访问的人出发做一次BFS统计连通分量个数。这样做当然也对但代码量大得多而且每次都要重新遍历图。并查集只需要一遍扫描加合并代码简洁效率也高。这道题还有一个变体如果好友关系是动态增加的每次增加后都要查询朋友圈数量。用BFS的话每次都要重新算而并查集只需要在合并时更新count变量查询是O(1)的。这就是并查集在动态场景下的优势。4.2 冗余连接用并查集检测环这道题是这样的给出一棵树的n条边实际上是一棵树多了一条边形成了环要求找出那条多余的边使得删掉它之后图变成一棵树。如果有多个答案返回最后出现的那条。思路很直接遍历每条边如果两个端点已经连通说明这条边就是多余的它形成了一个环如果还没连通就合并它们。def find_redundant_connection(edges): n len(edges) uf UnionFind(n 1) # 节点编号1到n for u, v in edges: if uf.connected(u, v): return [u, v] uf.union(u, v) return []这道题的精髓在于在一棵树中任意两个节点之间恰好有一条路径。如果加入一条边后两个节点已经连通那这条边必然形成环。并查集的connected操作正好能O(1)判断连通性。我第一次做这道题的时候想的是用DFS检测环每次加边后跑一遍DFS。后来发现并查集只需要一遍遍历而且不需要建图。从那以后凡是遇到“动态加边判断环”的题目我都优先考虑并查集。这道题还有一个进阶版本如果图不是树加一条边而是任意图要求找出所有形成环的边。思路是一样的只是不能提前返回要把所有冗余边都收集起来。4.3 岛屿数量并查集的二维应用这道题是LeetCode上的经典题目给一个由1陆地和0水组成的二维网格计算岛屿的数量。岛屿由水平或垂直方向上相邻的陆地连接而成。常规做法是DFS或BFS但并查集也能做而且思路很清晰。把每个1看作一个元素遍历网格如果当前格子是1检查它的右边和下边避免重复如果是1就合并。最后统计有多少个不同的根节点就是岛屿数量。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 i in range(rows): for j in range(cols): if grid[i][j] 0: water_count 1 continue # 只检查右边和下边避免重复 if i 1 rows and grid[i 1][j] 1: uf.union(i * cols j, (i 1) * cols j) if j 1 cols and grid[i][j 1] 1: uf.union(i * cols j, i * cols j 1) return uf.get_count() - water_count这里有一个细节水域格子也被初始化成了独立的集合所以最后要用总集合数减去水域格子数。另一种做法是只对陆地格子建并查集但需要额外的映射代码更复杂。我倾向于前者简单直接。这道题用并查集做的时间复杂度和DFS一样都是O(rows * cols * α)。但并查集的优势在于如果网格是动态变化的比如某些格子从水变成陆地并查集可以增量更新而DFS需要重新计算。这就是所谓的“动态连通性”问题。4.4 等式方程的可满足性并查集的逻辑推理这道题很有意思给出一组等式和不等式判断是否存在一种变量赋值使得所有式子同时成立。比如[ab, b!c, ac]就是不可满足的因为ab且ac推出bc与b!c矛盾。解题思路分两步先把所有等式用并查集合并然后检查所有不等式如果不等式两边的变量在同一个集合里就矛盾了。def equations_possible(equations): uf UnionFindDict() # 第一步处理所有等式 for eq in equations: if eq[1] : uf.union(eq[0], eq[3]) # 第二步检查不等式 for eq in equations: if eq[1] !: if uf.find(eq[0]) uf.find(eq[3]): return False return True这道题的关键洞察是等式具有传递性可以用并查集维护等价类不等式只需要检查两边是否在同一个等价类中。先处理等式再处理不等式的顺序很重要因为等式合并后不等式的检查才有意义。这道题让我意识到并查集不仅能处理图论问题还能处理逻辑推理问题。凡是涉及“等价关系”的场景并查集都是一个强有力的工具。等价关系有三个性质自反性、对称性、传递性。并查集天然满足这三个性质。4.5 带权并查集处理有距离的关系前面讲的都是普通的并查集只能回答“是否连通”。但有些题目需要回答“连通的距离是多少”。比如经典的“食物链”问题A吃BB吃CC吃A给出若干关系判断有多少句假话。这类问题需要用带权并查集。每个节点除了父指针还维护一个权值表示它与父节点的某种关系。在查找过程中权值会累加最终得到它与根节点的关系。带权并查集的find操作需要同时更新权值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要求weight[y] - weight[x] w root_x self.find(x) root_y self.find(y) if root_x root_y: return self.weight[x] - self.weight[y] w self.parent[root_x] root_y self.weight[root_x] self.weight[y] w - self.weight[x] return True带权并查集的难点在于权值更新的公式推导。以“食物链”为例权值0表示同类1表示吃2表示被吃。合并时的公式需要根据具体问题的语义来推导。我建议初学者先掌握普通并查集等遇到需要维护关系的题目时再学带权并查集。不要一上来就啃带权版本容易劝退。5. 常见问题与排查技巧实录5.1 并查集问题速查表问题现象可能原因排查方法解决方案结果偏大忘记合并某些关系检查遍历逻辑是否覆盖所有边补全合并操作结果偏小合并了不该合并的检查条件判断加连通性检查数组越界编号从1开始但开了n大小打印最大编号开n1或统一减一递归爆栈树太深且用递归find打印树高度改用迭代find多组数据错误忘记重置并查集检查每组是否new对象每组重新初始化性能不达标没有路径压缩检查find实现加上路径压缩字典版本慢哈希开销大对比数组版本改用数组映射5.2 我踩过的三个坑第一个坑是在union之前忘记find。有一次我写代码直接比较两个元素是否相等来判断是否合并结果当然错了。并查集判断的是根节点是否相同不是元素本身是否相同。这个错误很低级但在赶时间的时候真的会犯。第二个坑是路径压缩写错导致死循环。迭代版路径压缩的第二步如果写错了指针更新的顺序可能导致x在原地打转。我当时的错误写法是先把parent[x]改成root然后x parent[x]结果x变成了root循环条件永远不满足。正确的做法是先用临时变量保存next再更新。第三个坑是在需要判断环的题目中先union再判断。正确的顺序是先判断connected如果已经连通说明形成环否则再union。顺序反了就会漏掉环。避坑技巧写完并查集代码后用一个小例子手动模拟一遍。比如3个元素合并1和2再合并2和3然后查询1和3是否连通。手动走一遍find和union的流程能发现大部分逻辑错误。5.3 什么时候不该用并查集并查集虽然强大但也不是万能的。以下几种情况不适合用并查集需要删除边并查集只支持加边不支持删边。如果题目需要动态删边需要用更复杂的数据结构比如动态树。需要查询路径信息并查集只维护连通性不维护路径的具体信息。如果需要知道两点之间的最短路径得用BFS或最短路算法。需要方向性并查集处理的是无向关系。如果关系有方向比如A指向B并查集就不适用了。需要频繁查询集合内元素并查集不维护集合内的元素列表如果需要枚举集合内所有元素需要额外维护。理解这些限制能帮你在合适的场景选择并查集不合适的场景果断换方案。5.4 面试中的并查集考察点根据我的面试经验并查集相关的面试题通常考察以下几个层面第一层是基本实现。面试官会让你手写一个并查集考察你对parent数组、find、union的理解。这一层只要模板背熟就没问题。第二层是优化原理。面试官会问路径压缩和按秩合并的原理以及为什么能把复杂度降到O(α(n))。这一层需要理解摊还分析的基本思想。第三层是问题建模。面试官给一个实际问题你需要识别出它是连通性问题然后转化为并查集。这一层最难需要大量练习才能培养出直觉。第四层是变体应用。比如带权并查集、可持久化并查集、二维并查集等。这一层属于加分项不是每个面试都会问到。我的建议是前两层必须扎实第三层多刷题培养感觉第四层了解即可遇到再深入。5.5 刷题路线建议如果你刚开始学并查集我建议按以下顺序刷题朋友圈/省份数量入门理解基本操作冗余连接理解环检测岛屿数量二维应用等式方程的可满足性逻辑推理最长连续序列并查集哈希食物链带权并查集每道题做完后不要只看答案要自己手动模拟一遍并查集的变化过程。画图把每次find和union后的树结构画出来这样能加深理解。我当初学并查集的时候把每道题的并查集变化过程都画在了纸上。画了十几道题之后基本上看到题目就能条件反射地想到并查集。这个笨办法很有效推荐你也试试。6. 并查集的扩展与进阶方向6.1 可持久化并查集普通并查集只维护当前状态如果题目需要查询历史某个时刻的连通性就需要可持久化并查集。实现方式是用可持久化数组维护parent并且不能用路径压缩因为路径压缩会修改历史版本只能用按秩合并。可持久化并查集的复杂度是O(log^2 n)比普通并查集慢但能支持版本回溯。这类题目在竞赛中偶尔出现面试中很少考。6.2 并查集与其它数据结构的结合并查集经常和别的数据结构结合使用。比如并查集链表可以在合并集合的同时维护集合内的元素顺序并查集堆可以在合并集合的同时维护集合内的最值并查集字典树可以处理字符串的连通性问题。我做过一个项目需要把相似的字符串分组。做法是用字典树找相似关系然后用并查集合并。这种组合思路在工程中很常见。6.3 并查集在工程中的应用并查集不只是刷题用的实际工程中也有很多应用。比如图像处理连通区域标记把相邻的相似像素合并成区域。网络管理判断两台主机是否在同一个子网中。编译器优化变量等价类分析把等价的变量合并。社交网络好友推荐找出可能认识的人。游戏开发地图连通性判断比如判断两个区域是否可达。我在一个图像处理项目中用并查集做连通区域标记代码量比BFS少了三分之二性能还更好。从那以后凡是遇到连通性问题我都会先考虑并查集。6.4 并查集的性能调优经验如果你在工程中使用并查集有几个性能调优的点值得注意第一用数组而不是字典。数组的随机访问是O(1)且常数很小字典有哈希开销。如果元素编号连续一定用数组。第二路径压缩用迭代不用递归。迭代版本没有函数调用开销也没有栈溢出风险。第三按秩合并的rank可以用size代替。用集合大小作为合并依据效果和rank差不多而且size还能用于其它统计。第四批量操作时减少find调用。比如合并多个元素时可以先找到所有根节点再统一合并减少重复find。第五预分配数组。如果知道元素数量上限提前分配好数组避免动态扩容。这些优化在数据量大的时候效果明显。我实测过在100万数据规模下优化后的并查集比朴素版本快5倍以上。6.5 一个完整的工程级并查集实现最后给一个我在工程中使用的并查集实现支持泛型元素、路径压缩、按秩合并、连通分量统计class UnionFind: def __init__(self, elementsNone): self.parent {} self.rank {} self.count 0 if elements: for e in elements: self.add(e) def add(self, x): if x not in self.parent: self.parent[x] x self.rank[x] 0 self.count 1 def find(self, x): self.add(x) root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: self.parent[x], x root, self.parent[x] return root 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]: root_x, root_y root_y, root_x self.parent[root_y] root_x if self.rank[root_x] self.rank[root_y]: self.rank[root_x] 1 self.count - 1 return True def connected(self, x, y): return self.find(x) self.find(y) def get_count(self): return self.count def get_groups(self): groups {} for x in self.parent: root self.find(x) groups.setdefault(root, []).append(x) return list(groups.values())这个版本支持动态添加元素适合元素种类不确定的场景。get_groups方法可以枚举所有连通分量在某些题目中很有用。我在实际项目中使用这个实现处理过百万级别的数据性能完全够用。如果你有更极致的性能需求可以把字典换成数组但大多数场景下字典版本已经足够了。并查集这个数据结构入门容易精通也不难但真正用好需要大量的练习和实战。我建议你把这篇文章里的模板和例题都亲手敲一遍然后找十几道相关题目刷一刷。刷完之后你会发现自己对连通性问题的敏感度明显提升很多以前觉得复杂的题目现在一眼就能看出是并查集的变体。这种直觉就是刷题和实战积累出来的。