1. 项目概述为什么并查集是“数据结构中的瑞士军刀”如果你刷过一些算法题或者研究过图论相关的算法大概率会碰到一种场景给你一堆元素需要你动态地判断它们是否属于同一个集合或者需要你把两个集合合并起来。比如社交网络里判断两个人是不是间接好友通过共同好友连接游戏里判断两个像素点是否连通编译器里判断变量名是否属于同一个作用域。乍一看你可能觉得用数组标记一下或者用哈希表存一下关系就行。但一旦数据量上来操作变得频繁这种简单粗暴的方法效率就会急剧下降甚至成为性能瓶颈。这时候就该并查集Union-Find Set登场了。我第一次在工程里用上它是在处理一个千万级用户关系的实时推荐系统里。当时需要实时判断任意两个用户是否在同一个社交圈子里最初用深度优先搜索DFS去遍历关系图结果接口响应时间直接飙到秒级完全不可用。后来换成了并查集查询操作的时间复杂度近乎常数问题迎刃而解。从那以后我就把它当成了解决“动态连通性”问题的首选工具。简单来说并查集是一种用于管理元素分组情况的数据结构。它主要支持两种高效操作查找Find某个元素属于哪个集合以及合并Union两个元素所在的集合。它的核心思想非常巧妙用树形结构来组织集合每个集合用一棵树代表树根就是这个集合的“代表元”。判断两个元素是否同属一个集合就看它们的根是否相同合并两个集合就是把一棵树的根挂到另一棵树的根下面。并查集的美妙之处在于通过一些优化手段主要是路径压缩和按秩合并它能把这两种操作的平均时间复杂度优化到接近O(1)的水平。这对于需要处理海量动态连接数据的场景来说简直是“降维打击”。无论你是准备面试算法题还是在实际开发中遇到需要高效处理分组、连通、等价关系的问题花点时间吃透并查集绝对是笔稳赚不赔的投资。接下来我们就从最基础的原理开始一步步拆解它的实现、优化和应用。2. 核心原理与数据结构设计理解并查集关键在于抓住它的两个核心操作和其背后的树形模型。我们不要把它想得太复杂它本质上就是维护了一个森林若干棵树。2.1 用数组表示的树父指针表示法并查集最常用也最简洁的实现方式是使用一个一维数组。数组的下标代表每一个元素而数组里存储的值代表这个元素的“父节点”。对于一个元素来说如果它自己就是某个集合的根代表元那么我们就约定它在数组中的值指向自己或者用一个特殊值如-1表示。举个例子假设我们有6个元素编号0到5。初始时每个元素各自为一个独立的集合。我们可以用一个数组parent来表示parent[i] i 表示元素i的父节点就是它自己即它是自己所在集合的根。初始的parent数组就是[0, 1, 2, 3, 4, 5]。这代表了6棵只有一个节点的树。为什么用数组因为访问数组元素是O(1)的操作这为我们后续的优化打下了基础。同时元素编号数组下标本身就是一种隐式的映射我们不需要额外维护元素到其所在集合的映射关系。2.2 查找Find操作寻根问祖查找操作的目的是给定一个元素x找到它所在集合的根节点代表元。最朴素的做法就是沿着父指针一直向上找直到找到一个父节点是自己的节点即根节点。def find_naive(x): while parent[x] ! x: # 只要当前节点不是根 x parent[x] # 向上移动到父节点 return x这个过程就像是一个人追溯自己的家族族长一层层问“你的上级是谁”直到问到族长本人。时间复杂度分析在最坏情况下这棵树可能退化成一条链比如1-2-3-4-5根是5。这时查找元素1就需要遍历整条链时间复杂度为O(n)n是元素个数。这显然不是我们想要的。2.3 合并Union操作认祖归宗合并操作的目的是给定两个元素x和y将它们所在的集合合并成一个集合。操作步骤是分别找到x和y的根节点rootX和rootY。如果rootX rootY说明它们本来就在同一个集合无需操作。否则将其中一棵树的根节点指向另一棵树的根节点。即parent[rootX] rootY或parent[rootY] rootX。def union_naive(x, y): rootX find_naive(x) rootY find_naive(y) if rootX ! rootY: parent[rootX] rootY # 将rootX的父节点设为rootY合并后原来以rootX为根的整棵树都成为了以rootY为根的树的子树。潜在问题如果总是随意地将一棵树挂到另一棵树上比如总是把rootX挂到rootY上那么很可能在多次合并后树会变得越来越高甚至退化成链表。这会导致后续的find操作越来越慢。注意这里的“合并”是集合意义上的合并而不是把两个元素直接连接起来。合并后原来两个集合中的所有元素现在都共享同一个根节点从而属于同一个大集合。3. 优化策略从O(n)到近乎O(1)的魔法朴素实现的问题在于树可能变得很不平衡。并查集有两个经典的优化策略它们通常结合使用能将操作的平均时间复杂度优化到阿克曼函数的反函数级别对于任何在现实宇宙中可能遇到的数据规模这个值都小于5因此可以认为是近乎常数时间。3.1 路径压缩Path Compression这是针对find操作的优化。核心思想是既然我辛辛苦苦从x找到了根root那么我能不能顺便把这条路径上所有节点的父指针都直接指向root呢这样下次再查找这些节点时一步就能直达根节点。实现通常用递归非常优雅def find(x): if parent[x] ! x: # 如果不是根 parent[x] find(parent[x]) # 递归查找根并沿途将父节点设置为根 return parent[x] # 返回根递归的过程可以这样理解find(parent[x])会一直递归到根然后每一层递归返回时都会执行parent[x] 返回的根。最终x及其路径上的所有节点的parent都直接指向了根。还有一种非递归的迭代写法思路是两次遍历第一次找到根第二次把路径上所有节点的父节点都改成根。def find_iterative(x): root x while parent[root] ! root: # 第一次遍历找到根 root parent[root] # 第二次遍历进行路径压缩 while parent[x] ! root: next_node parent[x] parent[x] root x next_node return root实操心得在大多数编程语言的递归实现中路径压缩的递归写法简洁明了是首选。但在极深递归可能导致栈溢出的场景虽然并查集经过路径压缩后树很浅不太会发生或者追求极致性能时可以考虑迭代写法。我个人的经验是递归写法在99%的场景下都足够好。3.2 按秩合并Union by Rank这是针对union操作的优化。核心思想是在合并两棵树时总是将“矮”的树接到“高”的树下面这样能避免树的高度不必要的增加从而保持树的平衡。我们需要一个额外的数组rank秩来记录以每个节点为根的树的高度上界注意不是精确高度。初始时每个节点都是独立的树高度为0或1定义不同效果等价所以rank[i] 0。合并时找到两个根rootX,rootY。比较它们的rank。如果rank[rootX] rank[rootY]则将rootX挂到rootY下。因为矮树接入高树高树的高度不会增加。如果rank[rootX] rank[rootY]则将rootY挂到rootX下。如果rank[rootX] rank[rootY]则任意选择一方挂到另一方下但被挂接的树的rank需要加1。因为两棵高度相同的树合并新树的高度会增加1。def union(x, y): rootX find(x) rootY find(y) if rootX rootY: return # 按秩合并 if rank[rootX] rank[rootY]: parent[rootX] rootY elif rank[rootX] rank[rootY]: parent[rootY] rootX else: # 秩相等 parent[rootY] rootX rank[rootX] 1 # 只有秩相等时新的根秩才需要1为什么叫“秩”而不是“高度”因为经过路径压缩后树的高度会变化但我们维护的rank值在路径压缩时并不会更新这是一个“懒”更新。它更像是一个合并优先级的历史记录而不是当前精确的高度。但这并不影响按秩合并的正确性和高效性。重要提示路径压缩和按秩合并是正交的可以同时使用。它们共同作用是并查集效率的保证。只使用路径压缩最坏情况下的单次操作复杂度也是对数级两者结合才能达到近乎常数级的平均复杂度。4. 完整实现与代码剖析下面我们给出一个完整的、经过优化的并查集类实现并附上详细的注释。这个模板适用于绝大多数场景你可以直接复制使用。class UnionFind: 并查集 (Union-Find) 数据结构实现 支持路径压缩和按秩合并优化 def __init__(self, n: int): 初始化并查集包含 n 个独立元素 (0 到 n-1) :param n: 元素个数 self.parent list(range(n)) # 初始时每个元素的父节点是自己 self.rank [0] * n # 初始秩为0 self.count n # 当前连通分量集合的个数 def find(self, x: int) - int: 查找元素 x 所在集合的根节点代表元 使用递归实现路径压缩 :param x: 元素索引 :return: 根节点索引 if self.parent[x] ! x: # 递归查找根并直接将父节点指向根路径压缩 self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x: int, y: int) - bool: 合并元素 x 和 y 所在的集合 使用按秩合并优化 :param x: 元素索引 :param y: 元素索引 :return: 如果 x 和 y 原本不在同一集合合并成功返回 True否则返回 False 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]: 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 self.count - 1 return True def connected(self, x: int, y: int) - bool: 判断元素 x 和 y 是否属于同一集合 :param x: 元素索引 :param y: 元素索引 :return: 在同一集合返回 True否则 False return self.find(x) self.find(y) def get_count(self) - int: 获取当前连通分量集合的数量 :return: 连通分量数量 return self.count代码关键点解析初始化 (__init__):self.parent list(range(n))是Pythonic的写法生成了[0, 1, 2, ..., n-1]的列表。self.count是一个非常有用的字段用于实时跟踪当前有多少个独立的集合在解决一些特定问题如计算岛屿数量时可以直接使用无需再次遍历。查找 (find): 递归实现是路径压缩最清晰的表达。注意它修改了self.parent[x]这是“压缩”发生的地方。合并 (union): 返回bool值是一个实用设计调用者可以知道此次合并是否实际发生了。self.count的更新逻辑是只有两个元素原本不在同一集合即root_x ! root_y时合并才发生集合总数才减少1。判断连通性 (connected): 这是一个便捷方法内部直接调用find比较根节点。获取集合数量 (get_count): 直接返回维护的self.count效率是O(1)。使用示例uf UnionFind(10) # 10个元素0~9 print(uf.connected(1, 2)) # False初始都不连通 uf.union(1, 2) print(uf.connected(1, 2)) # True uf.union(2, 3) print(uf.connected(1, 3)) # True传递性 print(uf.get_count()) # 8合并了两次集合数从10变为85. 经典应用场景与实战解析理解了原理和实现我们来看看并查集到底能解决哪些实际问题。它绝不仅仅是算法题里的玩具。5.1 场景一朋友圈/社交网络LeetCode 547. 省份数量这是最经典的并查集应用题。问题描述通常是这样有n个城市给你一个n x n的矩阵isConnected表示城市间的直接相连关系。求“省份”的数量省份定义为直接或间接相连的城市组。解题思路初始化一个包含n个城市的并查集。遍历矩阵的上三角或下三角避免重复如果isConnected[i][j] 1说明城市i和j直接相连将它们合并 (union(i, j))。遍历结束后并查集中剩余的独立集合数量 (get_count()) 就是省份的数量。为什么用并查集因为“间接相连”定义了等价关系传递性。并查集正是为高效处理这种动态的等价关系合并与查询而生的。如果用DFS/BFS你需要为每个未访问的城市做一次遍历代码稍显复杂。而并查集的代码非常简洁直观。5.2 场景二岛屿问题变种LeetCode 305. 岛屿数量 II经典岛屿问题是静态网格而这个变种是动态的给你一个m x n的空网格然后按顺序添加k个陆地位置。要求你在每次添加一个位置后实时返回当前网格中的岛屿数量。解题思路初始化一个大小为m * n的并查集但初始时所有位置都是水可以特殊处理或者初始集合数为0。还需要一个二维数组grid标记当前位置是否是陆地。每添加一个位置(r, c)先将该位置标记为陆地。在并查集中“激活”这个位置可以理解为新增一个集合或者将其父节点设为自己。查看其上下左右四个邻居。如果邻居是陆地就将当前新位置与邻居位置进行合并 (union)。每次合并成功岛屿数量集合数就会减少1。添加新陆地可能使岛屿数量1孤立新岛也可能不变连接到现有岛甚至可能-1连接了两个原本分离的岛。记录每次操作后的岛屿数量。并查集的优势动态维护连通分量数量是并查集的强项。get_count()方法可以O(1)时间给出答案。如果使用DFS/BFS每次添加后都需要对整个网格或局部进行搜索时间复杂度会高很多。5.3 场景三检测无向图中的环给定一个无向图判断图中是否存在环。这是并查集在图论中的一个经典应用。算法步骤适用于边列表表示的图初始化并查集顶点数为n。遍历每条边(u, v)使用find查找u和v的根节点。如果根节点相同说明u和v在遍历到这条边之前就已经连通了。那么加上这条边必然形成一个环。立即返回True检测到环。如果根节点不同则使用union合并u和v所在的集合。遍历完所有边都没有发现环则返回False。原理对于无向图如果一条边的两个端点已经属于同一个连通分量那么这条边就是一条“多余”的边它一定会与已有的路径构成一个环。并查集在这个过程中动态地构建了图的连通分量并高效地检测了这种“多余”连接。5.4 场景四Kruskal最小生成树算法Kruskal算法是求加权无向图最小生成树MST的贪心算法。它的核心步骤是将所有边按权重从小到大排序然后依次尝试将边加入生成树如果加入这条边不会形成环就加入否则跳过。直到加入了n-1条边n为顶点数。并查集的作用判断“加入这条边是否会形成环”这正是上一小节的应用。Kruskal算法中并查集用于高效维护当前已选边构成的森林多个连通分量并判断新边的加入是否会导致森林中某棵树内部出现环即两个端点是否已在同一集合。这使得Kruskal算法的时间复杂度主要取决于边的排序O(E log E)而判断环的操作近乎O(1)。实操心得在实现Kruskal时并查集的union操作返回的bool值非常有用。如果union(u, v)返回True说明这条边被成功加入未成环可以累加其权重到MST总权重中并计数已选边数。代码清晰且高效。6. 常见问题、调试技巧与性能考量即使理解了原理在实际编码和调试中还是会遇到一些坑。这里分享几个我踩过的坑和总结的技巧。6.1 初始化时元素编号从0还是1开始这取决于你的问题输入。我们的模板默认从0开始。如果题目给的点编号是从1到n你有两种选择调整索引初始化UnionFind(n1)然后忽略下标0。在union或find时直接使用题目给的编号。这样逻辑简单但浪费了一个小空间。映射索引在调用并查集方法前将所有编号减1。例如uf.union(u-1, v-1)。这样更节省空间但需要小心处理所有输入。建议对于算法竞赛或面试空间通常不是瓶颈采用第一种方法更稳妥不易出错。在实际工程中如果数据规模极大可以考虑第二种。6.2 路径压缩的递归深度问题理论上经过路径压缩和按秩合并树的深度极小递归不会很深。但在一些极端古老的编程环境或对递归深度有严格限制的场景递归的find可能虽然概率极低导致栈溢出。解决方案使用迭代版本的find函数如3.1节所示。在Python中递归深度默认1000对于百万级别的元素经过优化后的树深远小于此值所以通常不用担心。但在C/C等环境中如果自己管理栈迭代版是更安全的选择。6.3 如何获取每个集合的所有成员标准的并查集只维护了父指针关系要获取某个集合的所有成员需要遍历所有元素对每个元素调用find然后根据根节点进行分组。这是一个O(n * α(n))的操作其中α(n)是阿克曼反函数。def get_sets(uf, n): sets {} for i in range(n): root uf.find(i) if root not in sets: sets[root] [] sets[root].append(i) return list(sets.values())如果业务中需要频繁查询集合成员并查集可能不是最佳选择可能需要结合其他数据结构。6.4 并查集能处理有向图吗标准的并查集是为无向的等价关系自反、对称、传递设计的。对于有向图关系可能不是对称的比如A指向B但B不指向A并查集无法直接处理。有些问题如判断有向图是否弱连通可以忽略方向将边视为无向再用并查集但这已经改变了原问题。6.5 性能实测与复杂度再认识虽然理论复杂度近乎O(1)但常数因子还是存在的。对于千万级甚至亿级的操作并查集的效率依然很高但编写时仍需注意初始化开销初始化parent和rank数组是O(n)的对于超大规模n这可能是一笔可观的开销。缓存友好性数组存储方式对CPU缓存友好这是它高效的原因之一。尽量保证对并查集的访问是顺序的或局部的。与DFS/BFS对比对于一次性、静态的连通性判断DFS/BFS的O(nm)n点m边可能比并查集的O(n * α(n) m)在常数上更小。但对于需要多次、动态增删边并查询的场景并查集的优势是决定性的。调试技巧当怀疑并查集逻辑出错时一个最有效的调试方法是打印出parent数组的状态。在每次union操作后打印出parent观察树的合并过程是否符合预期。这比单步调试更直观。