1. 项目概述为什么并查集是算法工程师的“瑞士军刀”如果你刷过LeetCode或者准备过技术面试大概率在“岛屿数量”、“朋友圈”这类题目里见过它。我第一次系统学习并查集是在准备一个图论相关的项目时需要高效处理数千万个节点的连通性问题。当时试过用深度优先搜索DFS去遍历结果内存直接爆了程序跑了几分钟还没出结果。后来导师扔给我一句“试试并查集。” 改完之后同样的数据集处理时间从分钟级降到了秒级。那一刻我才真正体会到这个看似简单的数据结构在处理某些特定问题时威力有多大。并查集英文叫Union-Find或者Disjoint-Set。它的核心功能极其专注高效地管理一堆元素的分组情况主要支持两种操作——“合并”两个集合以及“查询”某个元素属于哪个集合。听起来是不是简单得有点过分但正是这种“简单”让它成为了解决动态连通性问题的“神器”。你可以把它想象成江湖上的门派管理一开始每个人都是独行侠自成一派后来两个人看对眼了决定合并门派Union操作你想知道某个人到底属于武当派还是少林派就去查一下他的“祖师爷”是谁Find操作。并查集要解决的就是如何让“合并门派”和“查询祖师爷”这两件事做得飞快。它的应用场景远不止刷题。在我经历过的项目中从社交网络的好友关系推荐判断两个人是否属于同一个社交圈子到电路板自动布线中的网络连通性检查再到图像处理中的像素区域标记甚至是一些游戏开发中怪物群体的AI逻辑都能看到并查集的身影。它不追求大而全而是在一个非常垂直的领域——集合的合并与查询——做到了极致的高效。理解并掌握它就像是给你的算法工具箱里添了一把趁手、专用的螺丝刀面对特定问题时能让你事半功倍。2. 核心思想与抽象模型如何用数组表示“门派关系”并查集的精妙之处在于它用了一种非常“反直觉”但极其高效的方式来组织数据。我们通常认为要表示一组元素的归属应该用一个列表或者字典显式地存储每个元素所在的集合。但并查集走了另一条路它使用树形结构并且只关心每个元素的“父节点”是谁最终通过“根节点”来代表一个集合。2.1 从数组到森林的映射最经典、也是最基础的实现是使用一个长度为n的数组parent。这里n是元素的总数。数组的下标代表元素本身的编号比如012...n-1而数组parent[i]存储的值代表元素i的“父节点”是谁。初始化时我们认为每个元素都是独立的自己就是一个集合同时也是这个集合的根。所以我们让每个元素的父节点指向自己parent[i] i。这就像江湖初开每个人都自立门户自己是自己的掌门人。查询Find操作的目标是找到元素i所在集合的“根”即掌门人。方法就是沿着parent数组一路向上“认爹”直到找到一个父节点是自己的元素parent[x] x这个x就是根节点。例如我们想知道元素3的掌门人是谁就去看parent[3]假设是5再看parent[5]假设是5自己那么5就是根。这个过程就是一次树的遍历。合并Union操作的目标是把元素i和元素j所在的两个集合合并成一个。注意不是合并两个元素而是合并它们背后的整个门派。最直接的想法是先分别找到i和j的根节点root_i和root_j。如果它们相同说明本来就在一个集合里无需操作。如果不同我们就把其中一个根节点的父指针指向另一个根节点比如执行parent[root_i] root_j。这样两棵树就变成了一棵树两个集合合并成了一个。注意这里有一个非常关键的细节。合并时我们操作的是两个集合的根节点而不是i和j本身。直接parent[i] j是初学者常犯的错误这只会把i个人“过继”给j所在的门派而不是合并两个门派逻辑是完全错误的。2.2 一个具象化的例子假设我们有5个人0, 1, 2, 3, 4。初始状态parent [0, 1, 2, 3, 4]。合并(0, 1)找到0的根是01的根是1。把0的根指向1即parent[0] 1。现在parent [1, 1, 2, 3, 4]。集合情况{0,1}, {2}, {3}, {4}。合并(2, 3)找到2的根是23的根是3。把2的根指向3即parent[2] 3。parent [1, 1, 3, 3, 4]。集合{0,1}, {2,3}, {4}。查询(0)是否与(2)连通找0的根。parent[0]1,parent[1]1所以根是1。找2的根parent[2]3,parent[3]3根是3。根不同所以不连通。合并(1, 2)找到1的根是12的根是3。把1的根指向3即parent[1] 3。parent [1, 3, 3, 3, 4]。现在集合变成了{0,1,2,3}, {4}。再次查询(0)与(2)找0的根。parent[0]1,parent[1]3,parent[3]3根是3。找2的根parent[2]3,parent[3]3根是3。根相同所以连通。这个模型直观地展示了并查集是如何工作的。但是如果只是这样实现在极端情况下比如一直把新集合合并到某个长链的末尾树会退化成一条长长的链表这时Find操作的时间复杂度会退化到O(n)效率非常低。这就需要我们引入下面要讲的优化技巧。3. 性能优化核心路径压缩与按秩合并基础的并查集在糟糕的合并顺序下会变得很慢。幸运的是有两个堪称“神来之笔”的优化技巧可以保证并查集的操作效率接近常数时间。它们是并查集真正强大的核心所在。3.1 路径压缩让每个人都“认祖归宗”路径压缩Path Compression优化发生在Find操作中。回想一下我们找根的过程从当前节点开始一步一步往上跳。路径压缩的想法是既然我费劲找到了根为什么不顺便把沿途所有人的“爹”都直接改成根呢这样下次再查询他们中的任何一个时一步就能直达根节点。实现通常有两种方式递归压缩和迭代压缩。递归压缩代码简洁是教科书中最常见的形式。def find(x): if parent[x] ! x: # 如果x不是根 parent[x] find(parent[x]) # 递归找根并把x的父节点设为根 return parent[x] # 返回根这行parent[x] find(parent[x])是精髓。在递归返回的过程中从根节点开始回溯地把路径上每个节点的父指针都直接指向了最终的根。迭代压缩有时担心递归深度过大虽然经过压缩后很难出现可以用迭代方式。def find(x): root x while parent[root] ! root: # 先找到根root root parent[root] # 第二次遍历进行压缩 while parent[x] ! x: old_parent parent[x] parent[x] root x old_parent return root实操心得在绝大多数情况下递归压缩完全够用而且代码更清晰。除非你在一个递归栈深度受限的极端环境或者用某些不支持尾递归优化的语言处理超大数据否则优先用递归写法。路径压缩带来的性能提升是巨大的经过几次操作后整个树会变得非常扁平。3.2 按秩合并避免树长成“高个子”路径压缩主要优化了Find而按秩合并Union by Rank则是在Union操作时进行优化目的是避免合并后树的高度不必要的增加。这里的“秩”Rank可以粗略理解为树的高度的一个上界。我们需要一个额外的数组rank初始时每个元素的秩为0或1表示只有自己。 当合并两个根节点root_x和root_y时比较它们的秩。将秩较小的树的根指向秩较大的树的根。这样合并后整体树的高度不会增加如果两棵树秩不同或者仅增加1如果两棵树秩相同。如果两棵树秩相同则合并后新的根的秩需要加1。def union(x, y): root_x find(x) root_y find(y) if root_x root_y: return # 按秩合并 if rank[root_x] rank[root_y]: parent[root_x] root_y elif rank[root_x] rank[root_y]: parent[root_y] root_x else: # 秩相同时任意指向但被指向的根秩要加1 parent[root_y] root_x rank[root_x] 1为什么这样做有效想象一下如果你总是把高的树接到矮的树下那么合并后的树会变得更高。而按秩合并保证了我们总是让矮的树“依附”于高的树从而有效地控制了整棵树的最大高度。树的高度越小Find操作即使在没有路径压缩的情况下需要遍历的节点就越少。重要提示“秩”并不完全等于树的精确高度特别是在应用了路径压缩之后树的高度会被动态改变。因此rank更像是一个估计值或优先级用于在合并时做出更优的决策。在实际编码中我们通常只维护rank数组而不去动态更新每个节点精确的高度因为路径压缩会让高度信息很快失效维护精确高度的开销得不偿失。3.3 双剑合璧的复杂度当路径压缩和按秩合并同时使用时并查集的每个操作Find和Union的平均时间复杂度可以看作是阿克曼函数Ackermann Function的反函数。这个函数增长极其缓慢对于任何在宇宙可观测范围内有实际意义的输入规模比如10^600这个值都不会超过5。因此在工程实践中我们通常认为并查集的操作是近似常数时间复杂度 O(α(n))的其中α(n)是那个增长慢到离谱的反阿克曼函数。这意味着你可以对数以亿计的元素进行数百万次的合并和查询操作而总耗时依然非常低。这种效率是其他数据结构如每次合并都遍历整个集合难以企及的。4. 完整实现与代码剖析理解了原理和优化我们来动手实现一个工业级的并查集类。我会用Python来演示因为其语法清晰但逻辑完全适用于其他语言。4.1 类结构设计与初始化一个健壮的并查集类通常包含以下核心部分parent列表存储每个节点的父节点。rank列表存储每个根节点的秩高度上界。count变量可选记录当前不相交集合的数量在解决“岛屿数量”等问题时非常有用。class UnionFind: def __init__(self, n): 初始化并查集。 :param n: 元素的总数编号从 0 到 n-1。 self.parent list(range(n)) # 初始时每个元素的父节点是自己 self.rank [0] * n # 初始时每个元素的秩为0 self.count n # 初始时有n个独立的集合 def find(self, x): 查找元素x所在集合的根节点同时进行路径压缩。 :param x: 元素编号 :return: 根节点编号 # 递归实现路径压缩 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] # 以下是迭代实现路径压缩的版本供参考 # root x # while self.parent[root] ! root: # root self.parent[root] # # 路径压缩 # while self.parent[x] ! x: # old_parent self.parent[x] # self.parent[x] root # x old_parent # return root def union(self, x, y): 合并元素x和元素y所在的集合。 :param x: 元素编号 :param y: 元素编号 :return: 如果x和y原本就在同一集合返回False否则合并后返回True。 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 self.count - 1 # 集合数量减少一个 return True def is_connected(self, x, y): 判断元素x和元素y是否属于同一个集合。 :param x: 元素编号 :param y: 元素编号 :return: True 如果连通否则 False return self.find(x) self.find(y) def get_count(self): 获取当前不相交集合的数量。 :return: 集合数量 return self.count4.2 关键代码行解读与避坑指南__init__中的list(range(n))这是创建[0, 1, 2, ..., n-1]列表最快最清晰的方式。确保parent[i] i的初始状态。千万不要写成[0]*n那会让所有节点的父节点都是0。find函数中的递归调用self.parent[x] self.find(self.parent[x])这一行完成了查找和压缩两件事。递归会一直深入到根节点然后在回溯过程中将路径上每个节点的parent直接设置为根。这是并查集效率的灵魂代码。union函数中的return False/True这个返回值设计非常实用。在很多场景下比如Kruskal算法我们需要知道本次合并是否实际执行了即两个元素原本是否不在一个集合。这可以避免重复计数或无意义的操作。count的维护在union成功时self.count - 1。这个计数器在解决“连通分量计数”类问题时能省去最后再遍历一遍所有元素找根节点的开销直接O(1)获取答案。常见实现陷阱在union中忘记先find根节点直接操作x和y而不是root_x和root_y这是逻辑错误。按秩合并时只更新parent不更新rank当两棵树秩相同时必须将新根的rank加1否则rank就失去了衡量树高的意义。混用“秩”和“集合大小”有时你会看到“按大小合并”的优化它用集合的元素个数作为合并依据。这和“按秩合并”是两种不同的启发式策略虽然都能有效控制树高但不要在一个实现里混用两个数组一个叫rank一个叫size。选择一种并坚持下去。5. 经典应用场景实战解析懂了原理和实现我们来看看并查集到底能解决哪些实际问题。我挑选了几个最具代表性的场景它们也是面试中的高频考点。5.1 场景一LeetCode 547. 省份数量朋友圈问题问题描述有n个城市其中一些彼此相连另一些没有相连。如果城市a与城市b直接相连且城市b与城市c直接相连那么城市a与城市c间接相连。省份是一组直接或间接相连的城市。给你一个n x n的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连为0表示不直接相连。返回矩阵中省份的数量。并查集解法思路初始化一个大小为n的并查集每个城市自成一个集合。遍历矩阵的上三角或下三角因为矩阵是对称的。当isConnected[i][j] 1时说明城市i和j相连对它们执行union(i, j)操作。遍历结束后并查集中剩余的不相交集合的数量即get_count()就是省份的数量。代码实现def findCircleNum(isConnected): n len(isConnected) uf UnionFind(n) for i in range(n): # 只需遍历ji的部分避免重复和无意义的自连接(i,i) for j in range(i 1, n): if isConnected[i][j] 1: uf.union(i, j) return uf.get_count()为什么有效并查集完美地刻画了“连通关系”的传递性。一旦两个城市被合并它们就属于同一个“省份”集合。最终所有直接或间接相连的城市都会被合并到同一个集合中。集合的计数就是连通分量的计数。5.2 场景二LeetCode 200. 岛屿数量问题描述给你一个由1陆地和0水组成的二维网格。请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。并查集解法思路 这是一个二维网格的连通性问题。我们可以将每个陆地单元格视为一个元素。关键是如何将二维坐标映射到一维的并查集索引以及如何处理相邻合并。坐标映射对于一个m x n的网格单元格(r, c)可以映射到一维索引idx r * n c。初始化初始化一个大小为m * n的并查集。但注意我们只关心陆地1。一种技巧是初始化时只把陆地算作一个集合水格不算。更简单的方法是先全部初始化在遍历时如果遇到水格就将其从计数中扣除或者最后再统计陆地的根。遍历与合并遍历整个网格。当遇到一个陆地单元格时查看其右侧和下方的相邻单元格避免重复合并。如果相邻单元格也是陆地就将当前单元格与相邻单元格进行合并。统计结果遍历结束后统计所有陆地单元格中其根节点等于自身的数量即集合的代表元数量就是岛屿的数量。这需要遍历所有陆地单元格调用find。更高效的方法是在初始化时只统计陆地数量在合并成功时减少计数。优化实现def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) uf UnionFind(m * n) # 初始化水格不计入集合。我们先将count设为0遇到陆地再加。 # 但我们的UnionFind初始化需要总数。这里采用另一种常见策略先全部初始化最后只统计陆地的根。 # 为了效率我们修改UnionFind使其能处理“无效”节点。 water_count 0 for i in range(m): for j in range(n): if grid[i][j] 1: # 当前是陆地尝试与右、下邻居合并 idx i * n j # 向右合并 if j 1 n and grid[i][j1] 1: uf.union(idx, i * n (j 1)) # 向下合并 if i 1 m and grid[i1][j] 1: uf.union(idx, (i 1) * n j) else: water_count 1 # 统计岛屿数量即所有陆地单元格中根节点是自己的数量 roots set() for i in range(m): for j in range(n): if grid[i][j] 1: idx i * n j roots.add(uf.find(idx)) return len(roots)避坑点在网格问题中只向右和向下查找合并可以确保不重复处理相邻关系。如果向四个方向查找需要更小心地避免重复合并虽然并查集的union操作本身是幂等的但多余的查找和函数调用会影响性能。5.3 场景三Kruskal最小生成树算法这是并查集在图论算法中的经典应用。Kruskal算法用于在加权无向图中找出一棵最小生成树MST。算法步骤将图中所有边按权重从小到大排序。初始化一个并查集每个顶点自成一个集合。按权重从小到大遍历每条边(u, v, w)。使用并查集的find操作检查顶点u和v是否已经连通是否属于同一集合。如果不连通则这条边可以加入MST不会形成环执行union(u, v)合并两个顶点所在的集合并将边加入结果集。如果连通则跳过这条边加入它会形成环。当结果集中的边数达到顶点数-1时算法结束。并查集的核心作用高效地判断加入一条边后是否会形成环。如果u和v已经连通说明它们已经在同一棵生成树中再加入边(u, v)必然形成环。并查集的find操作近似O(1)的复杂度使得Kruskal算法总复杂度主要取决于边的排序O(E log E)效率非常高。def kruskal(n, edges): :param n: 顶点个数 :param edges: 边列表每个元素为 (u, v, w) :return: 最小生成树的边列表和总权重 uf UnionFind(n) edges.sort(keylambda x: x[2]) # 按权重排序 mst_edges [] total_weight 0 for u, v, w in edges: if uf.find(u) ! uf.find(v): # 判断是否连通 uf.union(u, v) # 合并集合 mst_edges.append((u, v, w)) total_weight w if len(mst_edges) n - 1: # 树已形成 break return mst_edges, total_weight6. 高级变种与实战技巧掌握了标准并查集你已经能解决80%的问题。但有些问题需要一些“变招”下面介绍两种常见的高级变种。6.1 带权并查集维护额外信息有时我们不仅需要知道元素是否连通还需要知道它们之间的某种“关系”或“距离”。例如在“食物链”、“判断等式方程的可满足性”等问题中元素之间存在相对关系。核心思想在parent数组之外再维护一个weight或distance数组用来记录当前节点到其父节点的“权值”或“偏移量”。在find和union操作中需要同步维护这个权值信息。经典例题LeetCode 399. 除法求值给你一个变量对数组equations和一个实数值数组values其中equations[i] [Ai, Bi]和values[i]共同表示等式Ai / Bi values[i]。再给你一些查询数组queries。如果存在答案返回答案否则返回-1.0。思路将每个变量看作一个节点。已知等式A / B k可以理解为A和B连通且A到B的“权值”是k。如果还有B / C m那么通过A-B-C这条路径我们可以推导出A / C k * m。这正好可以用带权并查集来维护。parent[x]记录x的父节点。weight[x]记录x / parent[x]的值。find(x)操作在路径压缩时需要更新weight[x]。例如x - p - root压缩后x - root新的weight[x]应该是(x/p) * (p/root) weight[x] * weight[p]。union(x, y, value)表示x / y value。需要先找到root_x和root_y然后将root_x的父节点设为root_y并根据x-root_x,y-root_y的路径权值以及x/yvalue这个关系计算出weight[root_x]的新值。这种并查集维护的是元素间的相对关系查询时通过比较两个元素到根节点的路径权值之比得到它们之间的关系。6.2 动态并查集支持动态添加元素标准的并查集初始化时需要确定元素个数。如果元素是动态出现的怎么办例如处理流式数据中的连通关系。解决方案使用字典HashMap代替数组。当遇到一个新元素时在字典中为其创建一个新条目父节点指向自己秩设为0。这样并查集就可以处理任意可哈希的元素如字符串、对象等而不仅仅是连续的整数索引。class DynamicUnionFind: def __init__(self): self.parent {} self.rank {} def find(self, x): if x not in self.parent: self.parent[x] x self.rank[x] 0 return 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] 16.3 实战调试与性能考量如何验证正确性对于复杂问题在实现后先用小规模数据手动模拟一遍画出parent和rank数组的变化图。或者编写简单的测试用例与一个更简单但低效的算法如BFS判断连通性的结果进行对比。性能瓶颈在哪里并查集本身的find和union操作极快。真正的性能瓶颈往往出现在外部排序如在Kruskal算法中对边列表的排序是O(E log E)。遍历如遍历整个网格或矩阵是O(N^2)或O(N)。因此优化重点应放在减少不必要的遍历和选择更优的外部算法上。空间复杂度标准实现需要两个长度为N的数组parent和rank空间复杂度为O(N)。对于动态并查集空间取决于实际出现的不同元素数量。一个常被忽略的优化在find函数的递归实现中Python的递归开销对于极深虽然并查集很难出现的调用栈可能是个问题。对于性能要求极其苛刻、且数据规模巨大的场景如竞赛可以考虑使用迭代路径压缩的版本或者使用sys.setrecursionlimit提高递归深度限制但这通常不是主要矛盾。并查集是一个“学起来简单用起来巧妙”的数据结构。它的代码模板非常短小精悍建议你把它背下来形成肌肉记忆。在遇到涉及分组、连通、传递性关系的问题时第一时间想想能不能用并查集来“秒杀”。很多时候它就是你从暴力解法通往高效解法的那座关键桥梁。