1. 项目概述为什么我们需要并查集如果你写过一些处理分组、连通性问题的代码比如社交网络的好友关系、游戏中的像素块合并或者检查一个网络中的节点是否连通你大概率会遇到一个经典困境如何高效地管理一堆元素并快速回答“这两个元素是不是一伙的”以及“把这两伙人合并成一伙”。用数组遍历时间复杂度太高。用链表合并操作又很麻烦。这时候并查集这个数据结构就该登场了。并查集英文叫 Union-Find 或 Disjoint-Set是一种专门用来处理不相交集合的合并与查询问题的树形数据结构。它的核心操作就两个Find查确定元素属于哪个集合和Union并合并两个集合。别看它概念简单在解决某些特定类型的问题时其效率之高足以让其他复杂数据结构望尘莫及尤其是在图论、网络连接、最小生成树Kruskal算法等场景中它是不可或缺的底层工具。我最初接触并查集是在刷算法题时遇到一道“岛屿数量”的题目。用深度优先搜索能做但代码写起来总感觉有些繁琐。后来了解到用并查集可以“边遍历边合并”思路异常清晰代码也简洁不少。从那以后但凡遇到涉及动态连通性的问题我第一个想到的就是它。这篇文章我就结合自己多年的使用和教学经验用大量的图示和模拟带你彻底吃透并查集从最基本的数组实现到路径压缩、按秩合并等优化技巧让你不仅会用更明白其背后的精妙设计。2. 核心思想与抽象模型把问题装进“集合”的框里在深入代码之前我们必须建立起正确的抽象模型。并查集处理的所有元素最初都被视为独立的集合。随着Union操作的进行一些集合被合并。我们需要随时能对任意两个元素执行Find操作判断它们是否属于同一个集合。2.1 如何表示“集合”——父指针表示法最直观的想法可能是给每个集合一个唯一的“老大”代表元。集合内的所有元素都指向这个“老大”。判断两个元素是否同属一个集合就看它们的老大是不是同一个人。合并两个集合就是让其中一个集合的老大认另一个集合的老大为新老大。在计算机中我们如何实现这种指向关系呢一个非常巧妙的做法是使用数组。假设我们有 n 个元素编号从 0 到 n-1。我们用一个长度为 n 的数组parent来表示。parent[i]存储的是元素 i 的“父节点”的索引。如果一个元素是它所在集合的“根”即老大那么我们就约定parent[i] i自己指向自己。初始时每个元素都是独立的集合所以元素: 0 1 2 3 4 parent:[0, 1, 2, 3, 4]此时每个元素都是自己的根。Find操作查找元素x的根。我们沿着parent[x]一直向上找直到找到一个满足parent[root] root的节点这个root就是x所在集合的代表元。Union操作合并元素x和y所在的集合。我们先分别找到x的根rootX和y的根rootY。如果rootX rootY说明它们本来就在一个集合无需操作。否则我们让其中一个根指向另一个根比如parent[rootY] rootX这样两个树就合并成了一棵。2.2 一个生动的类比江湖门派我们可以把并查集想象成一个江湖。最开始每个人元素都是一个独行侠自己创立了一个只有自己的小门派初始化自己是掌门。Find操作查相当于问一个人“你的掌门是谁”。他会说“我的掌门是A”如果A不是总掌门他会继续向上问直到找到那个“我的掌门就是我自己”的总掌门。Union操作并相当于两个门派合并。我们找到两个门派的总掌门然后让其中一个总掌门“归顺”另一个于是两个门派就合并了所有弟子都隶属于新的总掌门。这个模型非常简单但存在一个严重问题如果合并时总是随意让一个根指向另一个经过多次合并后这棵树可能会退化成一条很长的“链”。想象一下如果每次合并都让新门派归顺旧门派最终结构可能是一个总掌门下面挂着一长串的弟子像一条链表。这时执行Find操作就需要从叶子节点一路回溯到根节点时间复杂度退化为 O(n)这就失去了高效的意义。注意这个退化问题正是并查集优化的核心动机。后面要讲的“按秩合并”和“路径压缩”就是为了解决这个问题而生的。理解了这个痛点你就能明白那些优化技巧为何如此重要。3. 基础实现与性能瓶颈分析我们先来实现最基础的版本直观感受一下问题所在。3.1 初始化class UnionFind: def __init__(self, n): # 初始化每个元素的父节点指向自己 self.parent list(range(n))初始化操作的时间复杂度是 O(n)空间复杂度也是 O(n)。3.2 朴素的Find操作def find(self, x): # 不断向上查找直到找到根节点 while self.parent[x] ! x: x self.parent[x] return x在最坏情况下树退化为链find操作需要遍历整条链时间复杂度为 O(n)。3.3 朴素的Union操作def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX ! rootY: # 随意合并让rootY的根指向rootX self.parent[rootY] rootXunion操作主要耗时在两次find上因此其时间复杂度也是 O(n)。性能瓶颈演示 假设我们按顺序执行union(0,1),union(0,2),union(0,3), ...union(0, n-1)。 初始状态parent [0,1,2,3,...,n-1]执行union(0,1)找到root00,root11令parent[1]0。状态[0,0,2,3,...,n-1]执行union(0,2)找到root00,root22令parent[2]0。状态[0,0,0,3,...,n-1]... 最终parent [0,0,0,0,...,0]。这看起来是一棵以0为根的树但它的结构是星形的并非链。等等这里例子举得不对。让我们构造一个链 执行union(1,2),union(2,3),union(3,4)... 初始[0,1,2,3,4]union(1,2):find(1)1,find(2)2,parent[2]1-[0,1,1,3,4]union(2,3):find(2)2-1 (parent[2]1),find(1)1;find(3)3;parent[3]1-[0,1,1,1,4]union(3,4):find(3)3-1;find(4)4;parent[4]1-[0,1,1,1,1]在这个例子中树并没有退化成一条从叶子到根的单一链而是变成了一个深度为2的树根1孩子2,3,4。朴素的union策略总是让后一个的根指向前一个的根在某些序列下确实可能产生链但更典型的退化场景发生在总是将深度大的树作为子节点挂到深度小的树下时。为了专门演示退化可以考虑总是将新节点作为根然后让旧根指向它但这不符合我们通常的union逻辑。更准确的退化场景是如果我们总是将元素i与元素i1合并并且让i1的根指向i的根。union(0,1):parent[1]0(树0-1)union(1,2):find(1)0,find(2)2,parent[2]0(树0-1, 0-2)union(2,3):find(2)0,find(3)3,parent[3]0(树0-1, 0-2, 0-3) 这仍然是一个深度为1的树所有节点直接挂在根0下。要形成链我们需要让新合并的节点成为原来链的尾部。即合并时让一个集合的根指向另一个集合的非根节点。但标准的union操作是根与根之间的操作。所以朴素的、随意的根间合并我们例子中的方式并不必然产生深链但会产生不平衡的树。真正的性能问题在于随着合并树的深度可能会不断增加且没有控制。例如将深度大的树合并到深度小的树下面就会增加整体深度。关键在于我们必须认识到不加优化的合并可能导致树的高度深度线性增长从而使find操作变慢。为了优化我们需要两种策略按秩合并和路径压缩。4. 优化策略一按秩合并“秩”可以理解为树的高度的一个上界或估计值。我们引入一个rank数组rank[i]表示以i为根的树的秩。核心思想在合并两棵树时总是将秩较小的树合并到秩较大的树下。这样做的目的是避免增加整体树的高度。如果两棵树秩相等合并后新的根的秩需要加1。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 初始化秩为0 def find(self, x): # 暂时还是朴素查找 while self.parent[x] ! x: x self.parent[x] return x def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX rootY: return # 按秩合并 if self.rank[rootX] self.rank[rootY]: # rootX的树更矮把它挂到rootY下 self.parent[rootX] rootY elif self.rank[rootX] self.rank[rootY]: # rootY的树更矮把它挂到rootX下 self.parent[rootY] rootX else: # 两棵树一样高任意合并但新的根秩要1 self.parent[rootY] rootX self.rank[rootX] 1为什么这样有效如果rank[rootX] rank[rootY]将较矮的rootX树挂到较高的rootY树下rootY树的高度不会改变因为只是在一个叶子节点下加了一个子树最深路径没变。同理如果rank[rootX] rank[rootY]将rootY挂到rootX下rootX的高度不变。只有当两者秩相等时无论怎么挂新的树的高度都会比原来增加1因为两棵原树高度相同合并后根节点到最深叶子节点的路径长度增加了1。通过按秩合并可以保证树的高度大致以对数级别增长从而将find操作的时间复杂度从 O(n) 优化到 O(log n)。5. 优化策略二路径压缩按秩合并优化了树的生长但已经形成的路径可能仍然很长。路径压缩的想法更激进在每次执行find(x)的过程中我们既然费劲找到了根节点为什么不顺便把沿途的所有节点的父指针都直接指向根呢这样下次再查找这些节点时就能一步到位。路径压缩有两种常见的实现方式递归压缩和迭代压缩。5.1 递归式路径压缩这种方法在递归回溯的过程中直接修改父指针。def find(self, x): if self.parent[x] ! x: # 递归查找根并将沿途节点的父节点都设置为根 self.parent[x] self.find(self.parent[x]) return self.parent[x]这段代码非常简洁。它意味着如果x不是根那么就去找x的父节点的根并将找到的根同时设置为x的父节点。这个过程会递归进行最终整条路径上的节点在递归返回时都被“压平”直接指向了根。5.2 迭代式路径压缩两步法递归写法可能在某些语言或深度极大时存在栈溢出风险。迭代法更安全分为两步先找到根节点root。再从x开始将沿途所有节点的父节点都设置为root。def find(self, x): # 第一步找到根节点root root x while self.parent[root] ! root: root self.parent[root] # 第二步从x开始将沿途节点直接指向root while self.parent[x] ! root: parent_temp self.parent[x] self.parent[x] root x parent_temp return root还有一种更常见的迭代写法在寻找根的过程中同时进行部分压缩隔代压缩def find(self, x): while self.parent[x] ! x: # 将x的父节点指向其祖父节点路径压缩了一半 self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x这种方法不是一次性压缩到根而是每次上跳两级也能显著降低树高且代码更短。它被称为“隔代压缩”。路径压缩的威力经过路径压缩后find操作的摊还时间复杂度可以降低到接近 O(α(n))其中 α(n) 是阿克曼函数的反函数其增长极其缓慢对于任何实际可能遇到的 n 值α(n) 都不会超过 5。因此我们可以认为find和union操作几乎是常数时间。6. 完整优化版并查集实现与复杂度分析将按秩合并和路径压缩结合我们就得到了并查集的完全体。这里我选择递归路径压缩和按秩合并的组合因为代码最清晰。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [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): 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 self.rank[rootX] self.rank[rootY] return True # 合并成功 def is_connected(self, x, y): return self.find(x) self.find(y)复杂度分析时间复杂度单次find或union操作在应用了按秩合并和路径压缩后其摊还时间复杂度为 O(α(n))近似常数时间。空间复杂度O(n)用于存储parent和rank数组。实操心得在实际编码和面试中我强烈推荐使用这个“路径压缩 按秩合并”的模板。它效率高代码短几乎可以当作黑盒使用。注意rank数组在这里初始化为1表示树的初始大小节点数。在合并时我们将小树挂到大树下并更新大树的大小。这被称为“按大小合并”它和“按高度合并”即之前定义的秩在理论复杂度上是一样的都能有效避免树退化且“按大小合并”有时在某些问题中更方便比如需要知道集合的大小。7. 典型应用场景与实战解析理解了原理和实现我们来看看并查集能解决哪些实际问题。它的应用远超你的想象。7.1 场景一图的动态连通性问题这是并查集的“老本行”。给定一个图中的顶点边会动态添加需要频繁回答“顶点A和顶点B是否连通”。LeetCode 经典例题547. 省份数量问题有 n 个城市其中一些彼此相连一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市。给你一个 n x n 的矩阵 isConnected其中isConnected[i][j] 1表示第 i 个城市和第 j 个城市直接相连否则为 0。返回矩阵中省份的数量。思路每个城市是一个元素。遍历矩阵如果isConnected[i][j] 1就执行union(i, j)。最终省份的数量就是parent数组中根节点即parent[i] i的个数。代码要点初始化并查集大小为 n。遍历时只需遍历矩阵的上三角或下三角因为对称避免重复合并。最后遍历所有城市统计根节点数量。7.2 场景二最小生成树Kruskal算法Kruskal算法是贪心算法每次选取权重最小的边如果这条边连接的两个顶点不在同一个集合中即加入后不会形成环就加入生成树并合并这两个顶点所在的集合。这里“判断是否形成环”和“合并集合”正是并查集的用武之地。操作流程将所有边按权重从小到大排序。初始化一个包含所有顶点、无边的最小生成树以及一个大小为顶点数的并查集。遍历排序后的边对于每条边(u, v, w)如果find(u) ! find(v)说明 u 和 v 不在同一棵树中加入这条边不会形成环。将这条边加入最小生成树并执行union(u, v)。当最小生成树中的边数达到顶点数 - 1时算法结束。7.3 场景三处理岛屿类网格问题很多二维网格问题如计算岛屿数量、最大岛屿面积、被围绕的区域等可以用DFS/BFS解决但用并查集也有其独特优势尤其是需要动态合并或查询的场景。LeetCode 例题200. 岛屿数量DFS/BFS思路遍历网格遇到‘1’陆地就进行DFS/BFS标记所有相连的陆地岛屿数1。并查集思路将每个陆地格子看作一个元素。初始化时所有‘1’的格子都是独立的集合。遍历网格对于每个‘1’的格子检查其右方和下方的邻居避免重复如果邻居也是‘1’则执行union(当前格子, 邻居)。最终岛屿的数量就是独立的集合数量即parent中根节点的数量只统计对应格子为‘1’的。对比并查集思路在代码上可能稍复杂但其思想是“边遍历边合并”在处理某些变体问题如动态添加陆地时更灵活。7.4 场景四字符串等价关系朋友的朋友是朋友这类问题中元素之间存在一种等价关系如字符替换、句子相似性并查集可以用来维护这种等价类。LeetCode 例题839. 相似字符串组问题如果交换字符串 X 中的两个字母的位置就能得到字符串 Y那么称 X 和 Y 相似。给定一个字符串列表检查有多少个组其中每个组内的字符串彼此相似。思路每个字符串是一个元素。双重循环遍历所有字符串对判断它们是否相似即不同字符位置数是否为0或2。如果相似就union(i, j)。最终返回集合的数量。8. 常见问题、调试技巧与扩展即使掌握了模板在实际使用中还是会遇到一些坑。这里我总结几个常见问题和技巧。8.1 如何统计每个集合的大小或元素我们实现的模板中rank数组在“按大小合并”的策略下实际上存储的是以该节点为根的集合的元素个数前提是只在根节点的rank值有意义。因此要获取某个元素所在集合的大小只需找到它的根然后返回rank[root]即可。def get_size(self, x): root self.find(x) return self.rank[root]8.2 并查集能“拆开”已经合并的集合吗标准的并查集不支持高效的“分裂”操作。这是由它的数据结构特性决定的。一旦合并父指针就被修改要逆向拆开需要记录大量历史信息成本很高。如果问题中需要“断开”操作并查集可能不是最合适的数据结构需要考虑其他如动态图或线段树分治等高级技巧。8.3 初始化时元素编号从0还是1开始这完全取决于你的输入数据习惯。模板通常从0开始因为数组索引自然从0开始。如果题目给的点编号是1~N一种常见做法是初始化大小为n1然后忽略索引0或者将所有编号减1后再使用。务必保持统一否则极易出现数组越界错误。8.4 调试技巧可视化并查集状态当逻辑复杂时打印出parent数组可以帮助你快速定位问题。def debug_print(self): print(Index:, list(range(len(self.parent)))) print(Parent:, self.parent) print(Rank/Size:, self.rank) # 还可以打印每个集合 from collections import defaultdict sets defaultdict(list) for i in range(len(self.parent)): root self.find(i) # 注意要用find获取真正的根 sets[root].append(i) print(Sets:, dict(sets))8.5 带权并查集在一些更复杂的问题中元素之间不仅有连接关系还有权值关系如距离、差值等。这就需要带权并查集。它在普通并查集的基础上在parent数组之外再维护一个weight数组weight[i]表示从节点i到其父节点parent[i]的权值。在find进行路径压缩时需要同步更新权值在union时也需要根据题意计算两个根节点之间应该建立的权值关系。这是并查集的高级话题常见于“食物链”、“等式方程的可满足性”等问题。8.6 并查集的时间复杂度真的是常数吗我们常说的 O(α(n)) 是摊还时间复杂度。意思是执行一系列 m 个操作包含 n 个元素总的时间复杂度是 O(m * α(n))均摊到每个操作上就是 O(α(n))。对于单次操作最坏情况可能不是常数但在一系列操作的整体表现上其效率极高。在算法竞赛和工程中我们完全可以将其当作常数时间操作来信任。并查集是我工具箱里最喜爱的数据结构之一它用如此简单的思想父指针数组和巧妙的优化路径压缩、按秩合并解决了如此广泛的一类问题。掌握它不仅能让你在解决特定算法题时游刃有余更能深刻体会到计算机科学中“用简单组件构建强大抽象”的美妙。下次遇到需要处理分组、连通、等价关系的问题时不妨先想想能不能用并查集
1. 项目概述为什么我们需要并查集如果你写过一些处理分组、连通性问题的代码比如社交网络的好友关系、游戏中的像素块合并或者检查一个网络中的节点是否连通你大概率会遇到一个经典困境如何高效地管理一堆元素并快速回答“这两个元素是不是一伙的”以及“把这两伙人合并成一伙”。用数组遍历时间复杂度太高。用链表合并操作又很麻烦。这时候并查集这个数据结构就该登场了。并查集英文叫 Union-Find 或 Disjoint-Set是一种专门用来处理不相交集合的合并与查询问题的树形数据结构。它的核心操作就两个Find查确定元素属于哪个集合和Union并合并两个集合。别看它概念简单在解决某些特定类型的问题时其效率之高足以让其他复杂数据结构望尘莫及尤其是在图论、网络连接、最小生成树Kruskal算法等场景中它是不可或缺的底层工具。我最初接触并查集是在刷算法题时遇到一道“岛屿数量”的题目。用深度优先搜索能做但代码写起来总感觉有些繁琐。后来了解到用并查集可以“边遍历边合并”思路异常清晰代码也简洁不少。从那以后但凡遇到涉及动态连通性的问题我第一个想到的就是它。这篇文章我就结合自己多年的使用和教学经验用大量的图示和模拟带你彻底吃透并查集从最基本的数组实现到路径压缩、按秩合并等优化技巧让你不仅会用更明白其背后的精妙设计。2. 核心思想与抽象模型把问题装进“集合”的框里在深入代码之前我们必须建立起正确的抽象模型。并查集处理的所有元素最初都被视为独立的集合。随着Union操作的进行一些集合被合并。我们需要随时能对任意两个元素执行Find操作判断它们是否属于同一个集合。2.1 如何表示“集合”——父指针表示法最直观的想法可能是给每个集合一个唯一的“老大”代表元。集合内的所有元素都指向这个“老大”。判断两个元素是否同属一个集合就看它们的老大是不是同一个人。合并两个集合就是让其中一个集合的老大认另一个集合的老大为新老大。在计算机中我们如何实现这种指向关系呢一个非常巧妙的做法是使用数组。假设我们有 n 个元素编号从 0 到 n-1。我们用一个长度为 n 的数组parent来表示。parent[i]存储的是元素 i 的“父节点”的索引。如果一个元素是它所在集合的“根”即老大那么我们就约定parent[i] i自己指向自己。初始时每个元素都是独立的集合所以元素: 0 1 2 3 4 parent:[0, 1, 2, 3, 4]此时每个元素都是自己的根。Find操作查找元素x的根。我们沿着parent[x]一直向上找直到找到一个满足parent[root] root的节点这个root就是x所在集合的代表元。Union操作合并元素x和y所在的集合。我们先分别找到x的根rootX和y的根rootY。如果rootX rootY说明它们本来就在一个集合无需操作。否则我们让其中一个根指向另一个根比如parent[rootY] rootX这样两个树就合并成了一棵。2.2 一个生动的类比江湖门派我们可以把并查集想象成一个江湖。最开始每个人元素都是一个独行侠自己创立了一个只有自己的小门派初始化自己是掌门。Find操作查相当于问一个人“你的掌门是谁”。他会说“我的掌门是A”如果A不是总掌门他会继续向上问直到找到那个“我的掌门就是我自己”的总掌门。Union操作并相当于两个门派合并。我们找到两个门派的总掌门然后让其中一个总掌门“归顺”另一个于是两个门派就合并了所有弟子都隶属于新的总掌门。这个模型非常简单但存在一个严重问题如果合并时总是随意让一个根指向另一个经过多次合并后这棵树可能会退化成一条很长的“链”。想象一下如果每次合并都让新门派归顺旧门派最终结构可能是一个总掌门下面挂着一长串的弟子像一条链表。这时执行Find操作就需要从叶子节点一路回溯到根节点时间复杂度退化为 O(n)这就失去了高效的意义。注意这个退化问题正是并查集优化的核心动机。后面要讲的“按秩合并”和“路径压缩”就是为了解决这个问题而生的。理解了这个痛点你就能明白那些优化技巧为何如此重要。3. 基础实现与性能瓶颈分析我们先来实现最基础的版本直观感受一下问题所在。3.1 初始化class UnionFind: def __init__(self, n): # 初始化每个元素的父节点指向自己 self.parent list(range(n))初始化操作的时间复杂度是 O(n)空间复杂度也是 O(n)。3.2 朴素的Find操作def find(self, x): # 不断向上查找直到找到根节点 while self.parent[x] ! x: x self.parent[x] return x在最坏情况下树退化为链find操作需要遍历整条链时间复杂度为 O(n)。3.3 朴素的Union操作def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX ! rootY: # 随意合并让rootY的根指向rootX self.parent[rootY] rootXunion操作主要耗时在两次find上因此其时间复杂度也是 O(n)。性能瓶颈演示 假设我们按顺序执行union(0,1),union(0,2),union(0,3), ...union(0, n-1)。 初始状态parent [0,1,2,3,...,n-1]执行union(0,1)找到root00,root11令parent[1]0。状态[0,0,2,3,...,n-1]执行union(0,2)找到root00,root22令parent[2]0。状态[0,0,0,3,...,n-1]... 最终parent [0,0,0,0,...,0]。这看起来是一棵以0为根的树但它的结构是星形的并非链。等等这里例子举得不对。让我们构造一个链 执行union(1,2),union(2,3),union(3,4)... 初始[0,1,2,3,4]union(1,2):find(1)1,find(2)2,parent[2]1-[0,1,1,3,4]union(2,3):find(2)2-1 (parent[2]1),find(1)1;find(3)3;parent[3]1-[0,1,1,1,4]union(3,4):find(3)3-1;find(4)4;parent[4]1-[0,1,1,1,1]在这个例子中树并没有退化成一条从叶子到根的单一链而是变成了一个深度为2的树根1孩子2,3,4。朴素的union策略总是让后一个的根指向前一个的根在某些序列下确实可能产生链但更典型的退化场景发生在总是将深度大的树作为子节点挂到深度小的树下时。为了专门演示退化可以考虑总是将新节点作为根然后让旧根指向它但这不符合我们通常的union逻辑。更准确的退化场景是如果我们总是将元素i与元素i1合并并且让i1的根指向i的根。union(0,1):parent[1]0(树0-1)union(1,2):find(1)0,find(2)2,parent[2]0(树0-1, 0-2)union(2,3):find(2)0,find(3)3,parent[3]0(树0-1, 0-2, 0-3) 这仍然是一个深度为1的树所有节点直接挂在根0下。要形成链我们需要让新合并的节点成为原来链的尾部。即合并时让一个集合的根指向另一个集合的非根节点。但标准的union操作是根与根之间的操作。所以朴素的、随意的根间合并我们例子中的方式并不必然产生深链但会产生不平衡的树。真正的性能问题在于随着合并树的深度可能会不断增加且没有控制。例如将深度大的树合并到深度小的树下面就会增加整体深度。关键在于我们必须认识到不加优化的合并可能导致树的高度深度线性增长从而使find操作变慢。为了优化我们需要两种策略按秩合并和路径压缩。4. 优化策略一按秩合并“秩”可以理解为树的高度的一个上界或估计值。我们引入一个rank数组rank[i]表示以i为根的树的秩。核心思想在合并两棵树时总是将秩较小的树合并到秩较大的树下。这样做的目的是避免增加整体树的高度。如果两棵树秩相等合并后新的根的秩需要加1。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 初始化秩为0 def find(self, x): # 暂时还是朴素查找 while self.parent[x] ! x: x self.parent[x] return x def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX rootY: return # 按秩合并 if self.rank[rootX] self.rank[rootY]: # rootX的树更矮把它挂到rootY下 self.parent[rootX] rootY elif self.rank[rootX] self.rank[rootY]: # rootY的树更矮把它挂到rootX下 self.parent[rootY] rootX else: # 两棵树一样高任意合并但新的根秩要1 self.parent[rootY] rootX self.rank[rootX] 1为什么这样有效如果rank[rootX] rank[rootY]将较矮的rootX树挂到较高的rootY树下rootY树的高度不会改变因为只是在一个叶子节点下加了一个子树最深路径没变。同理如果rank[rootX] rank[rootY]将rootY挂到rootX下rootX的高度不变。只有当两者秩相等时无论怎么挂新的树的高度都会比原来增加1因为两棵原树高度相同合并后根节点到最深叶子节点的路径长度增加了1。通过按秩合并可以保证树的高度大致以对数级别增长从而将find操作的时间复杂度从 O(n) 优化到 O(log n)。5. 优化策略二路径压缩按秩合并优化了树的生长但已经形成的路径可能仍然很长。路径压缩的想法更激进在每次执行find(x)的过程中我们既然费劲找到了根节点为什么不顺便把沿途的所有节点的父指针都直接指向根呢这样下次再查找这些节点时就能一步到位。路径压缩有两种常见的实现方式递归压缩和迭代压缩。5.1 递归式路径压缩这种方法在递归回溯的过程中直接修改父指针。def find(self, x): if self.parent[x] ! x: # 递归查找根并将沿途节点的父节点都设置为根 self.parent[x] self.find(self.parent[x]) return self.parent[x]这段代码非常简洁。它意味着如果x不是根那么就去找x的父节点的根并将找到的根同时设置为x的父节点。这个过程会递归进行最终整条路径上的节点在递归返回时都被“压平”直接指向了根。5.2 迭代式路径压缩两步法递归写法可能在某些语言或深度极大时存在栈溢出风险。迭代法更安全分为两步先找到根节点root。再从x开始将沿途所有节点的父节点都设置为root。def find(self, x): # 第一步找到根节点root root x while self.parent[root] ! root: root self.parent[root] # 第二步从x开始将沿途节点直接指向root while self.parent[x] ! root: parent_temp self.parent[x] self.parent[x] root x parent_temp return root还有一种更常见的迭代写法在寻找根的过程中同时进行部分压缩隔代压缩def find(self, x): while self.parent[x] ! x: # 将x的父节点指向其祖父节点路径压缩了一半 self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x这种方法不是一次性压缩到根而是每次上跳两级也能显著降低树高且代码更短。它被称为“隔代压缩”。路径压缩的威力经过路径压缩后find操作的摊还时间复杂度可以降低到接近 O(α(n))其中 α(n) 是阿克曼函数的反函数其增长极其缓慢对于任何实际可能遇到的 n 值α(n) 都不会超过 5。因此我们可以认为find和union操作几乎是常数时间。6. 完整优化版并查集实现与复杂度分析将按秩合并和路径压缩结合我们就得到了并查集的完全体。这里我选择递归路径压缩和按秩合并的组合因为代码最清晰。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [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): 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 self.rank[rootX] self.rank[rootY] return True # 合并成功 def is_connected(self, x, y): return self.find(x) self.find(y)复杂度分析时间复杂度单次find或union操作在应用了按秩合并和路径压缩后其摊还时间复杂度为 O(α(n))近似常数时间。空间复杂度O(n)用于存储parent和rank数组。实操心得在实际编码和面试中我强烈推荐使用这个“路径压缩 按秩合并”的模板。它效率高代码短几乎可以当作黑盒使用。注意rank数组在这里初始化为1表示树的初始大小节点数。在合并时我们将小树挂到大树下并更新大树的大小。这被称为“按大小合并”它和“按高度合并”即之前定义的秩在理论复杂度上是一样的都能有效避免树退化且“按大小合并”有时在某些问题中更方便比如需要知道集合的大小。7. 典型应用场景与实战解析理解了原理和实现我们来看看并查集能解决哪些实际问题。它的应用远超你的想象。7.1 场景一图的动态连通性问题这是并查集的“老本行”。给定一个图中的顶点边会动态添加需要频繁回答“顶点A和顶点B是否连通”。LeetCode 经典例题547. 省份数量问题有 n 个城市其中一些彼此相连一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市。给你一个 n x n 的矩阵 isConnected其中isConnected[i][j] 1表示第 i 个城市和第 j 个城市直接相连否则为 0。返回矩阵中省份的数量。思路每个城市是一个元素。遍历矩阵如果isConnected[i][j] 1就执行union(i, j)。最终省份的数量就是parent数组中根节点即parent[i] i的个数。代码要点初始化并查集大小为 n。遍历时只需遍历矩阵的上三角或下三角因为对称避免重复合并。最后遍历所有城市统计根节点数量。7.2 场景二最小生成树Kruskal算法Kruskal算法是贪心算法每次选取权重最小的边如果这条边连接的两个顶点不在同一个集合中即加入后不会形成环就加入生成树并合并这两个顶点所在的集合。这里“判断是否形成环”和“合并集合”正是并查集的用武之地。操作流程将所有边按权重从小到大排序。初始化一个包含所有顶点、无边的最小生成树以及一个大小为顶点数的并查集。遍历排序后的边对于每条边(u, v, w)如果find(u) ! find(v)说明 u 和 v 不在同一棵树中加入这条边不会形成环。将这条边加入最小生成树并执行union(u, v)。当最小生成树中的边数达到顶点数 - 1时算法结束。7.3 场景三处理岛屿类网格问题很多二维网格问题如计算岛屿数量、最大岛屿面积、被围绕的区域等可以用DFS/BFS解决但用并查集也有其独特优势尤其是需要动态合并或查询的场景。LeetCode 例题200. 岛屿数量DFS/BFS思路遍历网格遇到‘1’陆地就进行DFS/BFS标记所有相连的陆地岛屿数1。并查集思路将每个陆地格子看作一个元素。初始化时所有‘1’的格子都是独立的集合。遍历网格对于每个‘1’的格子检查其右方和下方的邻居避免重复如果邻居也是‘1’则执行union(当前格子, 邻居)。最终岛屿的数量就是独立的集合数量即parent中根节点的数量只统计对应格子为‘1’的。对比并查集思路在代码上可能稍复杂但其思想是“边遍历边合并”在处理某些变体问题如动态添加陆地时更灵活。7.4 场景四字符串等价关系朋友的朋友是朋友这类问题中元素之间存在一种等价关系如字符替换、句子相似性并查集可以用来维护这种等价类。LeetCode 例题839. 相似字符串组问题如果交换字符串 X 中的两个字母的位置就能得到字符串 Y那么称 X 和 Y 相似。给定一个字符串列表检查有多少个组其中每个组内的字符串彼此相似。思路每个字符串是一个元素。双重循环遍历所有字符串对判断它们是否相似即不同字符位置数是否为0或2。如果相似就union(i, j)。最终返回集合的数量。8. 常见问题、调试技巧与扩展即使掌握了模板在实际使用中还是会遇到一些坑。这里我总结几个常见问题和技巧。8.1 如何统计每个集合的大小或元素我们实现的模板中rank数组在“按大小合并”的策略下实际上存储的是以该节点为根的集合的元素个数前提是只在根节点的rank值有意义。因此要获取某个元素所在集合的大小只需找到它的根然后返回rank[root]即可。def get_size(self, x): root self.find(x) return self.rank[root]8.2 并查集能“拆开”已经合并的集合吗标准的并查集不支持高效的“分裂”操作。这是由它的数据结构特性决定的。一旦合并父指针就被修改要逆向拆开需要记录大量历史信息成本很高。如果问题中需要“断开”操作并查集可能不是最合适的数据结构需要考虑其他如动态图或线段树分治等高级技巧。8.3 初始化时元素编号从0还是1开始这完全取决于你的输入数据习惯。模板通常从0开始因为数组索引自然从0开始。如果题目给的点编号是1~N一种常见做法是初始化大小为n1然后忽略索引0或者将所有编号减1后再使用。务必保持统一否则极易出现数组越界错误。8.4 调试技巧可视化并查集状态当逻辑复杂时打印出parent数组可以帮助你快速定位问题。def debug_print(self): print(Index:, list(range(len(self.parent)))) print(Parent:, self.parent) print(Rank/Size:, self.rank) # 还可以打印每个集合 from collections import defaultdict sets defaultdict(list) for i in range(len(self.parent)): root self.find(i) # 注意要用find获取真正的根 sets[root].append(i) print(Sets:, dict(sets))8.5 带权并查集在一些更复杂的问题中元素之间不仅有连接关系还有权值关系如距离、差值等。这就需要带权并查集。它在普通并查集的基础上在parent数组之外再维护一个weight数组weight[i]表示从节点i到其父节点parent[i]的权值。在find进行路径压缩时需要同步更新权值在union时也需要根据题意计算两个根节点之间应该建立的权值关系。这是并查集的高级话题常见于“食物链”、“等式方程的可满足性”等问题。8.6 并查集的时间复杂度真的是常数吗我们常说的 O(α(n)) 是摊还时间复杂度。意思是执行一系列 m 个操作包含 n 个元素总的时间复杂度是 O(m * α(n))均摊到每个操作上就是 O(α(n))。对于单次操作最坏情况可能不是常数但在一系列操作的整体表现上其效率极高。在算法竞赛和工程中我们完全可以将其当作常数时间操作来信任。并查集是我工具箱里最喜爱的数据结构之一它用如此简单的思想父指针数组和巧妙的优化路径压缩、按秩合并解决了如此广泛的一类问题。掌握它不仅能让你在解决特定算法题时游刃有余更能深刻体会到计算机科学中“用简单组件构建强大抽象”的美妙。下次遇到需要处理分组、连通、等价关系的问题时不妨先想想能不能用并查集
)
