企业官网建设流程全解析

并查集（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 的代表，过程如下：

1. 关键判定：树的根在 parent 中满足parent[x] == x；
2. 找到 0 的父亲parent[0]，是 1；
3. 1 的父亲parent[1]是 3，1 不是根，继续；
4. 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)为例，合并过程为：

1. 找到 0 的根节点 3；
2. 找到 7 的根节点 6；
3. 将 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 # 初始化 parent，size 和 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 / cnt，union 时"小的树挂到大的树上"）。547. 朋友圈（英文版题解） 中给出的 JavaUnionFind实现则是用rank数组替代size数组完成同样的按秩合并，并同样通过count--维护连通分量个数——两份实现互相印证了模板的正确性与可移植性。

带权并查集：维护节点间的相对关系

上面讲到的都是无权图，因此仅用 parent 表示节点指向关系即可。但如果数据带有"权"（距离、差值、比例、模运算结果等），除了 parent 指向关系，还需要维护节点间的权重关系。一个自然的做法是用另一个哈希表 weight 存储节点到其父节点的权重，例如weight[a] = 1表示 a 到其父节点的权重是 1。

带权并查集的 find 路径压缩与 union 合并会与无权版略有不同——因为我们不仅关心节点指向的变更，还关心权重如何随之更新。考虑如下场景：x 的父节点是 a，y 的父节点是 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): # 初始化 parent，weight 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。

最小生成树经典算法 Kruskal

Kruskal 算法被形象地称为加边法：每次选择权重最小的边加入结果集。为了防止环的产生，需要检查当前边是否已经让两端点联通——这正是并查集connected/union的用武之地。仓库 thinkings/graph.md 中给出了完整实现：

1. 对边按权值从小到大排序；
2. 将 n 个顶点初始化为 n 个联通域；
3. 按权值从小到大贪心选择边：若两端已联通则放弃，否则合并并累加权值；
4. 重复直到联通域大小为 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.md；
• 721. 账户合并——等价关系合并，见 721.accounts-merge.md；
• 990. 等式方程的可满足性——等式/不等式的联通与冲突判定；
• 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