并查集Union-Find完全指南联通性判定、路径压缩与带权合并的 LeetCode 实战【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode并查集Union-Find也叫 Disjoint Set是一种以树型结构处理不交集合并与查询问题的数据结构是解决两个点是否联通元素是否属于同一集合这类连通性/等价关系问题最常用、最高效的武器。本篇以仓库核心文档 thinkings/union-find.md 为骨架结合仓库内 547、721、1697、1168 等多道实战题解与 thinkings/graph.md 中的 Kruskal 实现从形象化的司令—军长—师长模型讲起逐步覆盖 find / union / connected 三大核心 API、路径压缩与按秩合并两大优化、带权并查集的权重推导最终给出可直接套用的代码模板与刷题清单。读完后你将能一眼识别连通、等价、同组类题目并熟练套用模板在 O(1) 均摊时间内完成查询。背景连通性问题的本质相信大家都玩过迷宫游戏——目标是从地图的一个角落移动到出口规则很简单只是不能穿墙。实际上找到一条从入口到出口的具体路径并不能直接用并查集解决。但如果把规则改成一个判断题——是否存在一条从入口到出口的路径——那么这就退化为一个简单的联通性问题Connectivity恰好可以借助本节要讲的并查集来完成。更妙的是如果地图保持不变而不断改变入口和出口的位置依次让你判断起点和终点是否联通此时并查集的效率会高得超出想象因为图结构固定后我们可以增量地合并所有可达区域后续每次查询都近乎 O(1)。并查集的应用也不局限于算法题。在人工智能领域它可以用于图像人脸识别把同一个人的不同角度、不同表情的面部数据联通起来从而很容易回答两张图片是否是同一个人无论拍摄角度和面部表情如何变化。概述树型数据结构与不交集并查集使用的是一种树型数据结构用于处理一些不交集Disjoint Sets的合并及查询问题。所谓不交集是指任意两个集合之间没有公共元素每个元素恰好属于一个集合。上面两个人是否间接认识两个地点之间是否有至少一条路径的例子其实都可以抽象为联通性问题如果两个点联通那么这两个点之间就存在至少一条路径。值得注意的是并查集只能回答联通与否而不能回答具体的联通路径是什么。若要回答具体路径则需要借助其他算法如广度优先遍历 BFS、Dijkstra 等。这是选择算法前必须想清楚的前提。形象解释司令、军长与师长为了直观理解并查集可以引入一个军队层级模型假设有若干司令司令下有若干军长军长下有若干师长师长下还有士兵……判断两个节点是否联通如何判断某两个师长是否归同一个司令管即连通性方法很简单顺着师长往上找找到司令。如果两个师长找到的是同一个司令那么他们就归同一个司令管假设这两人级别比司令低。同理判断两个士兵是否归同一个师长管也可以向上搜索到师长如果搜索到的两个师长是同一个就说明这两个士兵归同一个师长管。在代码层面我们用parent[x] y表示 x 的父节点是 y通过不断沿 parent 链向上搜索找到 root然后比较两者的 root 是否相同即可得出结论。这里的 root 就是上文提到的集合代表representative。之所以用parent存储每个节点的父节点而不是用children存储子节点是因为我们需要找到某个元素的代表也就是根——向上找根远比向下枚举子节点高效。这个不断往上找的操作一般称为find利用它可以轻松判断两个节点是否连通。合并两个联通区域假设现在有两个司令两个集合要将其合并为一个联通域。最简单的方式就是直接将其中一个司令指向另外一个也就是让一个集合的根成为另一个集合的根的子节点。合并后两个区域中所有元素的 find 结果都指向同一个根两个区域便联通了。以上就是并查集三个核心 API——find、connected和union——的形象化解释。核心 API数据结构与三个基本操作并查集Union-find Algorithm定义了两种核心操作Find确定元素属于哪一个子集可用于判断两个元素是否属于同一子集。Union将两个子集合并成同一个集合。为了精确定义这些方法需要先定义如何表示集合。一种常用策略是为每个集合选定一个固定的元素作为代表representative以表示整个集合。Find(x) 返回 x 所属集合的代表Union 则以两个集合的代表作为参数进行合并。初始时每个节点的代表都是它自己每个人的代表都是自己本身即每个点自成一个连通域。例如初始化后 parent 可能长这样注意parent[3] 3说明 3 是根{ 0: 1, 1: 3, 2: 3, 4: 3, 3: 3 }find向上找根假如要在上面的 parent 中找 0 的代表过程如下关键判定树的根在 parent 中满足parent[x] x找到 0 的父亲parent[0]是 11 的父亲parent[1]是 31 不是根继续3 的父亲parent[3]是 3 本身所以 3 就是我们要找的代表返回 3。这个向上追溯的过程具有明显的递归性可以用迭代或递归两种方式实现。迭代写法def find(self, x): while x ! self.parent[x]: x self.parent[x] return x递归写法带路径压缩def find(self, x): if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) return self.parent[x] return x这里的递归实现实际上做了路径压缩每次向上查找之后沿途节点都被直接指向根树的高度被压低理想情况下被压缩到 2 层左右。路径压缩有什么用每次 find 都会从当前节点不断向上搜索直到根其时间复杂度大致等于节点的深度。如果树的高度不受控制最坏情况下可能等于节点数find 的时间复杂度会退化为 $O(n)$。而做了路径压缩之后树的平均高度不会超过 $\log n$如果同时使用路径压缩与下面要讲的按秩合并find 的时间复杂度可以趋近 $O(1)$更严谨的说法是趋近阿克曼函数的某个反函数。极限情况下每一条路径都被压缩过此时继续查找的时间复杂度就是 $O(1)$。connected两个节点是否联通直接复用 find 即可如果两个节点的祖先代表相同那么它们就联通。def connected(self, p, q): return self.find(p) self.find(q)union合并两个联通区域将其中一个节点挂到另外一个节点的祖先上使两者的祖先相同两个节点即联通。以union(0, 7)为例合并过程为找到 0 的根节点 3找到 7 的根节点 6将 6 指向 3。其中第 3 步的6 指向 3而不是 3 指向 6并非随意选择为了使得合并之后的树尽可能平衡一般选择将小树挂载到大树上面3 的秩比 6 的秩大这就是所谓的按秩合并Union by Rank / by Size可以避免出现链状退化等极端情况。最简单的 union 实现不判断秩便于理清主脉络def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] self.find(q)不带权并查集完整代码模板平时做题遇到的更多是不带权的并查集实现相对简单。以下是本文推荐的高可用模板也是仓库多道题解中反复出现的结构class UF: def __init__(self, M): self.parent {} self.size {} self.cnt 0 # 初始化 parentsize 和 cnt # size 是一个哈希表记录每一个联通域的大小其中 key 是联通域的根value 是联通域的大小 # cnt 是整数表示一共有多少个联通域 for i in range(M): self.parent[i] i self.cnt 1 self.size[i] 1 def find(self, x): if x ! self.parent[x]: self.parent[x] self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return # 小的树挂到大的树上 使树尽量平衡 leader_p self.find(p) leader_q self.find(q) if self.size[leader_p] self.size[leader_q]: self.parent[leader_p] leader_q self.size[leader_q] self.size[leader_p] else: self.parent[leader_q] leader_p self.size[leader_p] self.size[leader_q] self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q)对模板中三个字段的理解parent记录每个节点的父节点指向parent[x] x表示 x 是根size记录每个联通域的大小key 为根value 为联通域内节点数供按秩合并使用保证小树挂大树cnt记录当前联通域的总个数。初始化时为 M每个点自成一个联通域每次成功 union 后自减 1最终cnt就是图中连通分量联通域的个数。该模板与仓库 1697. 检查边长度限制的路径是否存在 题解中的 UF 实现几乎一致同样维护 parent / size / cntunion 时小的树挂到大的树上。547. 朋友圈英文版题解 中给出的 JavaUnionFind实现则是用rank数组替代size数组完成同样的按秩合并并同样通过count--维护连通分量个数——两份实现互相印证了模板的正确性与可移植性。带权并查集维护节点间的相对关系上面讲到的都是无权图因此仅用 parent 表示节点指向关系即可。但如果数据带有权距离、差值、比例、模运算结果等除了 parent 指向关系还需要维护节点间的权重关系。一个自然的做法是用另一个哈希表 weight 存储节点到其父节点的权重例如weight[a] 1表示 a 到其父节点的权重是 1。带权并查集的 find 路径压缩与 union 合并会与无权版略有不同——因为我们不仅关心节点指向的变更还关心权重如何随之更新。考虑如下场景x 的父节点是 ay 的父节点是 b现在要将 x 和 y 合并a b ^ ^ | | | | x - y假设 x 到 a 的权重是 w(xa)y 到 b 的权重是 w(yb)x 到 y 的权重是 w(xy)。合并将 a 挂到 b 上之后a - b ^ ^ | | | | x y那么 a 到 b 的权重应该更新为多少由权重环路的可传导性可得w(xa) w(ab) w(xy) w(yb)因此w(ab) w(xy) w(yb) - w(xa)需要强调的是上述关系式是加法型示例具体是加法、减法、取模还是乘法、除法完全由题目决定。但无论采用哪种运算这种运算必须满足可传导性否则权重更新便无从推导。加法型带权并查集代码模板class UF: def __init__(self, M): # 初始化 parentweight self.parent {} self.weight {} for i in range(M): self.parent[i] i self.weight[i] 0 def find(self, x): if self.parent[x] ! x: ancestor, w self.find(self.parent[x]) self.parent[x] ancestor self.weight[x] w return self.parent[x], self.weight[x] def union(self, p, q, dist): if self.connected(p, q): return leader_p, w_p self.find(p) leader_q, w_q self.find(q) self.parent[leader_p] leader_q self.weight[leader_p] dist w_q - w_p def connected(self, p, q): return self.find(p)[0] self.find(q)[0]注意带权 find 的返回值为二元组(祖先, x 到祖先的累计权重)union 需要额外的参数dist表示题目给定的 p 与 q 之间的权重关系合并时通过dist w_q - w_p更新根的权重。这正是上面w(ab) w(xy) w(yb) - w(xa)公式的代码化表达。带权并查集的典型题目是399. 除法求值求a / b的值本质是把除法比例作为可传导权重进行合并与查询。这类题的关键词同样是关系/连通套路依然是套模板。复杂度分析令 n 为图中点的个数空间复杂度需要存储 parent带权并查集还有 weight空间复杂度取决于点的个数为 $O(n)$。时间复杂度并查集的时间消耗主要在 union 和 find 操作上。同时使用路径压缩 按秩合并后时间复杂度接近于 O(1)更严谨的表达式是 $O(\log(m \times \alpha(n)))$其中 n 为合并次数m 为查找次数α 是阿克曼Ackermann函数的某个反函数在现实中几乎可视为常数。如果只使用路径压缩或只使用按秩合并其中一种则两者时间复杂度分别为 $O(\log x)$ 和 $O(\log y)$其中 x、y 分别为合并与查找的次数。应用场景检测图是否有环思路遍历所有边将边进行合并在合并之前先判断两个端点是否已经联通如果合并前已经联通说明加入该边会形成环。uf UF() for a, b in edges: if uf.connected(a, b): return False uf.union(a, b) return True典型题目684. 冗余连接、Forest Detection。最小生成树经典算法 KruskalKruskal 算法被形象地称为加边法每次选择权重最小的边加入结果集。为了防止环的产生需要检查当前边是否已经让两端点联通——这正是并查集connected/union的用武之地。仓库 thinkings/graph.md 中给出了完整实现对边按权值从小到大排序将 n 个顶点初始化为 n 个联通域按权值从小到大贪心选择边若两端已联通则放弃否则合并并累加权值重复直到联通域大小为 n找到 n-1 条边。class DisjointSetUnion: def __init__(self, n): self.n n self.rank [1] * n self.f list(range(n)) def find(self, x: int) - int: if self.f[x] x: return x self.f[x] self.find(self.f[x]) # 路径压缩 return self.f[x] def unionSet(self, x: int, y: int) - bool: fx, fy self.find(x), self.find(y) if fx fy: return False if self.rank[fx] self.rank[fy]: fx, fy fy, fx self.rank[fx] self.rank[fy] self.f[fy] fx return True class Solution: def Kruskal(self, edges) - int: n len(points) dsu DisjointSetUnion(n) edges.sort() ret, num 0, 1 for length, x, y in edges: if dsu.unionSet(x, y): ret length num 1 if num n: break return ret注意这里的unionSet返回布尔值合并失败已在同一集合返回 False 表示会产生环合并成功返回 True。仓库内 1168. 水资源分配优化 正是 Kruskal 并查集的实战通过假想虚拟水源 0 号点把每家打井费用转化为0 → i的边随后对所有边按费用排序从小到大用 Union-Find 判断两节点是否连通、未连通则记录费用并合并最终得到全部住户通水的最小花费。计算连通分量个数547. 朋友圈省份数量 把好友关系矩阵视为无向图的邻接矩阵问题转化为求图中连通分量的个数。用并查集求解时遍历矩阵上三角的M[i][j] 1进行 union最终uf.count模板中的 cnt即为朋友圈数量。其英文题解 547. friend circles 还对比了 DFS、BFS、Union-Find 三种解法与复杂度指出带权按秩合并Union-Find 可避免最坏 O(n) 的退化时间复杂度为 $O(n^2\log n)$、空间复杂度 $O(n)$。离线排序查询1697. 检查边长度限制的路径是否存在 是并查集 排序优化离线查询的经典题把边按权值升序、查询按 limit 升序排序后遍历查询的同时将所有权值小于当前 limit 的边进行 union然后判断 pj 与 qj 是否已在同一联通域——若联通则路径上的所有边必定都小于 limit。由于排序打乱了查询索引需要记录原始下标。该题解中的 UF 类与本文模板完全一致路径压缩 按 size 合并时间复杂度 $O(m\log m q\log q)$。等价关系合并721. 账户合并 抛开 name 不管只根据 email 建立并查集同一连通分量中的 email 就是同一个人再用哈希表记录 email → name 的映射输出结果。题解中还指出一个重要的实战教训若不做路径压缩find/union/connected 最坏会退化到 $O(N)$而加上 size 按秩合并与 find 路径压缩后时间复杂度可降到 $O(1)$ 量级。947. 移除最多的同行或同列石头 则展示了如何把行/列相同抽象为联通关系以石头为节点同行或同列的石头互相联通答案是总石头数 - 联通区域数。这类题目正是文档所说官方没有贴并查集标签但用并查集极其简单的代表。仓库中其他并查集实战还包括 839. 相似字符串组、959. 由斜杠切分区域、785. 判断二分图、3108. 带权图的最小代价行走 等可在 problems 目录下按需查阅。练习清单与刷题建议关于并查集的题目LeetCode 官方标注的约为 30 道数据截至 2020-02-20但还有不少题目虽未贴并查集标签用并查集解决却非常简洁。掌握模板后刷这类题会非常快出错概率也大大降低这就是模板的好处。文档总结的经典练习如下仓库已收录题解的直接给出仓库路径547. 朋友圈省份数量——无权图连通分量计数见 547.number-of-provinces.md 与 547.friend-circles-en.md721. 账户合并——等价关系合并见 721.accounts-merge.md990. 等式方程的可满足性——等式/不等式的联通与冲突判定1202. 交换字符串中的元素——索引联通 分组排序1697. 检查边长度限制的路径是否存在——带权边 离线排序查询见 1697.checking-existence-of-edge-length-limited-paths.md。上面前四道都是无权图的连通性问题第五道是带权边权限制图的问题。两种类型都要掌握——题目关键字都是连通性代码都是套模板。看完本文建议立刻动手练习以上题目检测学习成果随后可继续挑战 1168 水资源分配优化最小生成树 并查集与 947 移除石头行列联通抽象等进阶题。总结识别特征如果题目中出现连通等价同组同环等关系就可以考虑并查集必备优化使用并查集时务必做路径压缩否则随着树的高度增加复杂度会逐渐增大若能同时配合按秩合并小树挂大树时间复杂度可趋近 O(1)带权并查集实现相对复杂难点在路径压缩和合并时权重的更新。只要把节点关系画成如下平行四边形示意图a - b ^ ^ | | | | x y再套用可传导的权重恒等式如加法型w(ab) w(xy) w(yb) - w(xa)就不难推导出正确的更新公式。本文提供的 UF 模板不带权版与带权版在仓库多道题解中反复使用union 时按 size 小树挂大树、find 时递归路径压缩、cnt 维护连通域个数。熟练背诵并理解这两套模板再配合上述练习清单你就能在连通性类题目上做到快速、准确、不易出错。延伸阅读本文主题相关的更多背景可参考仓库 thinkings/README.md 中的算法索引以及 thinkings/graph.md 中关于最小生成树Kruskal Prim的完整推导。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考