并查集入门：从力扣765情侣牵手理解Union-Find核心思想与建模

最近在力扣刷题765题“情侣牵手”的题目标签里赫然写着 union-find也就是并查集。很多朋友看到这题一脸懵换座位跟并查集有什么关系明明用贪心模拟交换也能做为什么非要用一个听起来这么抽象的数据结构其实这道题特别适合用来理解并查集的核心价值它不关心你怎么一步一步交换它只关心“这些坐错的人之间构成了几个互相纠缠的团体”。搞懂这个你就能直接写出答案公式最少交换次数 情侣对数 - 并查集连通分量数。这篇文章我会从并查集到底是干什么的开始讲然后一步步推导力扣765的建模过程把完整代码、底层的为什么、还有我实际提交时踩过的坑全部分享出来。适合刚接触并查集的算法新手也适合准备面试想快速复习的人。1. 先把并查集这东西的用途看明白1.1 并查集到底在解决什么问题并查集的全称是“不相交集合数据结构”英文是 Disjoint Set Union缩写为 DSU也叫 union-find。它从名字上就写得很直白union 是合并find 是查找。所以它的核心任务只有两个一是判断两个元素是否在同一个集合里二是把两个集合合并成一个。听起来很简单但它的厉害之处在于“动态维护连通性”。什么叫动态就是你不断地往系统里添加新的关系比如告诉你 a 和 b 是朋友又告诉你 b 和 c 是朋友这时候你自然知道 a 和 c 也能扯上关系。随时有人问你“a 和 c 是朋友吗”你都要能立刻回答。这种问题如果每次都用图遍历去搜一次就是 O(NM)关系一多就完全扛不住。而并查集经过优化后单次查询和合并的均摊复杂度趋近于 O(1)这个性能差距在实际使用中非常明显。并查集主要用来做什么的一句话总结处理一堆元素按照等价关系划分成若干个连通分量的问题。现实里的应用包括社交网络中的“朋友圈”划分、网络节点是否连通、Kruskal 算法求最小生成树、图片像素的连通区域标记、拼图游戏里碎片的分组等等。只要满足“两个东西之间存在一条关系链并且关系可以传递”大概率就能用并查集建模。1.2 为什么“情侣牵手”会用到并查集回到力扣 765。题目给了一个长度为 2n 的数组 rowrow[i] 表示坐在第 i 个座位的人的编号。编号规则是 0 和 1 是一对2 和 3 是一对4 和 5 是一对……也就是说编号 x 的人其情侣编号是 x ^ 1。我们最终的目标是让每一对情侣都坐在相邻的两个座位上问最少交换多少次。注意题目里一次交换可以交换任意两个人的座位不局限于相邻座位这个条件很重要。如果不限制相邻那么问题就变成了“如何用最少的交换次数把配对关系整理好”本质上是在处理一个置换的错位结构。这种错位结构不是随机散落的它会形成若干个闭合的“错误环”。比如 0 和 2 坐在一组相邻座位上1 和 3 坐在另一组相邻座位上。表面上只是两对情侣互相串了位实际上这四个座位上的两个人已经被绑定成了一个集团你只交换一次就能同时解决这两对情侣。并查集恰好擅长划分这种集团。一旦知道了整个座位数组里有多少个独立的错误集团答案也就出来了。这就是并查集为什么会出现在这道题的标签里的原因。2. 并查集的原理和基础代码5分钟过一遍2.1 三个核心操作并查集最简单的实现只需要一个数组 parent。parent[i] 表示元素 i 的父节点初始时每个元素都独自成一个集合所以 parent[i] i也就是自己指向自己。find(x)找到 x 所在集合的“代表元素”也叫根节点。做法是顺着 parent 链一路向上走直到某个节点的 parent 等于它自己。union(x, y)把 x 和 y 所在的集合并起来。做法是先 find 到两个根如果根不同就把其中一个根的 parent 指向另一个根。isConnected(x, y)判断 x 和 y 是否在同一个集合直接比较两个 find 的结果即可。这三个操作互相配合。union 依赖 findfind 依赖 parent 数组。想要并查集性能好优化点基本都落在 find 上因为如果树退化成一条长链find 就会变成 O(N)整个复杂度就崩了。2.2 用“门派”类比理解把每个集合看成一个江湖门派。每个门派都有一个掌门也就是根节点。两个弟子想知道自己是不是同一个门派就需要顺着自己的上级一路问到掌门然后比较掌门的编号。如果掌门是同一个人就是一个门派如果掌门不同那就比武合并输的一方掌门拜赢的一方掌门为师整个门派从此合并。这个类比可以帮你记住三个关键点。第一parent 数组存的是“上级”不是“掌门”所以查到一个节点时不代表它就是根。第二find 的任务是找到根而 union 的任务是让一个根变成另一个根的门下。第三路径压缩相当于“弟子问了一次掌门之后直接把上级改成掌门”以后再问就少走很多路。而按秩合并相当于“人数少的门派拜人数多的门派为师”让门派结构尽量扁平。2.3 一个可以直接复用的模板下面是我自己常用的 Python 并查集模板class UnionFind: def __init__(self, n): self.parent list(range(n)) self.count n def find(self, x): # 路径压缩边走边把节点挂到更靠近根的位置 while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False # 简单版直接合并按秩合并详见后文 self.parent[root_x] root_y self.count - 1 return True def connected(self, x, y): return self.find(x) self.find(y)这里的 count 记录的是当前并查集中有多少个集合。初始时有 n 个独立集合每成功 union 一次count 就减少 1。这个 count 在后面解 765 题时会直接用上。提示find 写成递归版本也可以但 Python 递归深度有限数据量大的时候建议使用循环版本避免系统栈溢出。3. 力扣765情侣牵手的完整解题过程3.1 题目精读座位、情侣编号、异或关系先统一一下术语。假设有 n 对情侣那么一共有 2n 个座位数组 row 长度是 2n。编号 0 到 2n-1 是人的编号。情侣关系有两个等价判断方法如果 a ^ 1 b那么 a 和 b 是情侣。如果 a // 2 b // 2那么 a 和 b 是情侣。异或 1 是一个位运算小技巧。二进制下0^111^102^133^124^155^14。这正好对应“相邻偶数和奇数是一对”的编号规则。用位运算判断情侣关系特别快写起来也很优雅。但我们建模时不直接用人的编号作为并查集节点而是把第 i 对情侣抽象成编号 i。也就是 person // 2。比如编号 0 和 1 的人属于情侣对 0编号 2 和 3 的人属于情侣对 1。这个映射是整道题的核心后续所有 union 操作都发生在“情侣对编号”这个维度上。3.2 核心建模把“必须坐在一起”当成连通关系我们从左到右把 row 数组按两个座位一组来扫描。每一组是两个相邻座位例如 row[0] 和 row[1] 是一组row[2] 和 row[3] 是一组。如果这一组的两个人 a 和 b 本身是情侣说明这组已经满足条件不做任何事。如果 a 和 b 不是情侣就说明这一组坐错了我们把 a // 2 和 b // 2 这两个情侣对编号 union 起来。为什么坐错了就要 union因为这两个人各自的情侣都被挤到别的组去了这两对情侣的命运被这一组座位绑定在一起。想要通过交换让大家都归位一定会在这些错位的情侣对之间产生交换关系。随着扫描进行多个错位的情侣对会通过一个个“错误小组”连成更大的团体。这个团体就是并查集里的一个连通分量。举个例子。假设 row [0, 2, 1, 3]n2。第一组座位是 0 和 2。0 的情侣应该是 1不是 2所以坐错。0//202//21执行 union(0, 1)。第二组座位是 1 和 3。1 的情侣应该是 0不是 3所以坐错。1//203//21再次 union(0, 1)。最后并查集只有 1 个连通分量count1答案 2 - 1 1。实际只需要交换 2 和 1得到 [0, 1, 2, 3]。再举一个已经满足条件的例子。row [0, 1, 2, 3]第一组是 0 和 1是情侣第二组是 2 和 3是情侣。两个组都跳过count 保持 2答案 2 - 2 0。这说明代码里用 a ! b 判断是否需要 union 是安全的。3.3 关键结论最小交换次数 情侣对数 - 连通分量数这个结论是题解里最常见的公式但很多人不理解。我来拆开讲。假设最终并查集有 cnt 个连通分量每个连通分量包含若干对情侣。第 i 个连通分量包含 k_i 对情侣那么所有 k_i 加起来等于总情侣对数 N。现在我们声称第 i 个连通分量内部最少只需要 k_i - 1 次交换就能让其中所有情侣相邻。为什么是 k_i - 1你可以把这个连通分量看作一个由错误座位关系编织成的网络。在这个网络里每对情侣都通过至少一个“错误相邻”与其他情侣对相连。如果分量里有 k 对情侣就意味着有 k 个节点通过错误关系连成了一个连通的闭环结构。要让 k 对情侣全部归位每正确交换一次最多只能让一对情侣彻底稳定下来而在一个包含 k 个节点的连通网络里至少需要 k-1 次这样的“修正”才能把所有闭环全部打开。更直接地说k 对情侣坐成一团乱麻时最少 k-1 次交换一定够少于 k-1 次则无法让所有情侣两两独立成组。把所有分量加起来总交换次数 Σ(k_i - 1) Σk_i - cnt N - cnt。这就是公式的由来。3.4 代码实现与逐行注释直接给完整代码from typing import List class UnionFind: def __init__(self, n): self.parent list(range(n)) self.count n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return self.parent[root_x] root_y self.count - 1 class Solution: def minSwapsCouples(self, row: List[int]) - int: n len(row) // 2 # 情侣对数 uf UnionFind(n) for i in range(0, len(row), 2): a row[i] // 2 # 左座位的人属于第几对情侣 b row[i 1] // 2 # 右座位的人属于第几对情侣 if a ! b: uf.union(a, b) return n - uf.count代码非常短但每一行都有意义。n 是情侣对数也是并查集的节点个数。遍历时步长为 2每次处理一组座位。a 和 b 是座位上的两个人所属的情侣对编号。如果 a ! b说明这一组坐的不是一对情侣需要 union。最后返回 n - uf.count就是公式的直接体现。如果你把代码从 Python 改成 Java 或 C结构完全不变。唯一要注意的是入参类型和 List 的引入其他没有任何特殊之处。3.5 贪心解法对比什么时候不用并查集其实 765 题还有一种更“暴力”的贪心解法从左往右扫描每一组座位如果遇到了不是情侣的一组就找到当前这个人对应的情侣的下标直接把它换到另一个座位上。这样每一组座位扫描完后这对情侣就固定了以后不会再被破坏。统计交换次数得到的结果同样是最优解。那既然贪心也能做为什么还要学并查集我的体会是并查集解法的优势在于“直接算不模拟”。它不需要真的去数组里找下标、做交换而是把问题的结构抽取了出来。代码更短逻辑也更接近数学公式。当你理解了“连通分量”这个概念后遇到其他类似题目比如计算需要多少次操作能让所有点连通、最少去掉几条边能分成若干连通块你也能很快迁移。而贪心解法虽然直观但如果题目稍作变形比如限制只能交换相邻座位贪心策略就需要重新推导并查集建模反而更容易调整。所以我建议两种解法都写一遍。贪心帮你理解“为什么最少交换次数可以这样构造”并查集帮你理解“答案的本质是一个计数公式”。两种视角互补面试时你可以根据现场灵感选择更顺手的那种。4. 踩坑记录并查集解题容易犯的5个错4.1 节点定义混乱parent 数组开错大小最常见的错是把 row.length 当作并查集的节点数。在 765 题中节点是“情侣对编号”不是“人的编号”。如果你直接 UnionFind(len(row))虽然 parent 数组大了但代码逻辑会变得非常别扭。更可怕的是有人用 row[i] 作为节点那 person 的范围是 0 到 2n-1又要跟 person//2 混在一起最后 count 统计出来完全对不上。我写题前会先问自己三个问题节点是什么边是什么最终要统计的量是什么这三个问题想清楚再动手。在 765 题里节点是情侣对编号边是“座位相邻且不是情侣”统计量是 N - 连通分量数。4.2 find 函数写错导致死循环一个很隐蔽的错是把路径压缩写成了下面这样def find(self, x): while self.parent[x] ! x: x self.parent[self.parent[x]] return x这段代码在某些情况下会让 x 跳到 parent[x] 的父节点但忽略了当前节点本身的指向更新一旦遇到两个节点互相指向就可能陷入死循环。排查方法很简单构造一个只有两个节点的并查集执行 union(0,1)然后调用 find(0)如果卡住或者返回值不对就是 find 写错了。最稳妥的还是用模板中的写法先更新当前节点的 parent 指向父节点的父节点再移动到新的位置。4.3 跳过路径压缩直接超时力扣 765 的数据量不算特别大但如果你养成不写路径压缩的习惯遇到“账户合并”那种百万级数据就会吃大亏。并查集如果没有路径压缩每次 find 最坏是 O(N)整体可能变成 O(N^2)。路径压缩的代码就一行parent[x] parent[parent[x]]它带来的收益却是巨大的。如果你还想再稳一点可以加上按秩合并用 size 数组记录集合大小把小的集合接到大的集合上。我个人的模板是def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return if self.size[rx] self.size[ry]: rx, ry ry, rx self.parent[ry] rx self.size[rx] self.size[ry] self.count - 14.4 把“判断情侣”和“合并情侣对”混为一谈处理每组座位时正确的逻辑是如果 a 和 b 是同一对情侣就跳过否则合并它们所属的情侣对编号。有人会在 if a ^ 1 b 时 continue然后用 a//2 和 b//2 做 union这没问题。但如果你看到不是情侣就直接 union(a, b)那就错了。因为 a 和 b 是人编号不是情侣对编号你等于在二维的人编号维度上建图最终统计出来的分量数跟答案公式对不上。记住一个小技巧凡是题目里出现“配对”概念先尝试把它映射成“下标除以二”或者“异或某个数”来表示同一组。一旦映射建立并查集的节点数通常会减半问题也会清晰很多。4.5 统计答案时减错了 count并查集里 count 是当前集合的数量。最终答案公式是 n - uf.count其中 n 是情侣对数也就是 len(row) // 2。有些同学代码里用变量 m 表示 len(row)最后写成 m - uf.count那答案就会永远偏大。命名不清晰是这类 bug 的根源。我习惯在代码开头就写好n len(row) // 2 uf UnionFind(n)这样后面直接用 n不会跟数组长度混淆。4.6 常见问题速查表症状可能原因解决建议find 死循环或返回值不对parent 更新顺序写错使用标准循环路径压缩模板答案比预期大节点数用了 len(row)节点数用 len(row) // 2运行超时没有路径压缩或按秩合并find 中加压缩union 中按大小合并答案偶尔对偶尔错把个人编号直接当作节点统一使用 person // 2count 没有维护union 成功后忘了 count - 1成功合并才减少 count5. 从这道题延伸出去并查集在真实场景中的价值5.1 Kruskal 最小生成树并查集最经典的搭档学图论的时候Kruskal 算法是并查集最出名的应用。做法是把所有边按权重从小到大排序然后依次遍历。对于每条边如果两个端点目前不在同一个连通分量里就把它们 union 起来并选入最小生成树。这里的“当前是否在同一个连通分量”就是并查集的 connected 操作。在 765 题里我们做的事跟 Kruskal 有异曲同工之妙都是在遍历一组潜在关系发现两个节点不在同一集合就执行合并。区别只是 Kruskal 要额外按权重排序而情侣牵手只需要按座位顺序扫描。所以如果你已经理解 Kruskal再看 765 题应该会有一种“原来如此”的熟悉感。5.2 动态连通性在线查询的救星很多问题不是一次性给你所有数据而是边操作边询问。比如在线游戏里的组队系统玩家 A 和 B 组队就 union(A, B)玩家 C 问自己是否和 D 同队就 find 对比根。这种场景如果用图存储每次新增一条边后都要重新计算连通分量代价很大。而并查集天然支持动态合并和查询每次操作都是几乎常数的时间。这也是它叫“动态连通性数据结构”的原因。你不需要预知所有关系关系可以一点一点加进来随时回答“连通吗”“有几个集合”这两个问题。5.3 高频面试题变体一览如果你准备面试下面这些题都值得用并查集刷一遍力扣 200 岛屿数量二维网格中相邻的 1 属于同一个岛屿用并查集合并相邻的 1最后统计集合数。力扣 684 冗余连接无向图中找一条多余的边删除后图仍然连通。按顺序 union第一次遇到两个端点已经连通的边就是答案。力扣 721 账户合并根据共同邮箱合并账户本质是集合合并最后输出每个集合的邮箱列表。力扣 1319 连通网络的操作次数求最少操作次数让所有计算机连通答案思路跟 765 的“总数减连通分量数”非常相似。你会发现这些题有一个共同模式给你一些元素和一些关系问你分成几组或者问需要几步连成一体。看到这种模式优先想到并查集。5.4 并查集不是银弹什么场景不适合并查集只擅长维护“连通性”不擅长维护集合内部的复杂信息。比如你想知道每个集合里具体有哪些成员想按某种顺序输出集合内容用并查集就不太方便。你可以用哈希表在 union 的时候顺手维护列表但那样会增加复杂度不如根据需求换用图遍历或者其他数据结构。还有一个常见限制并查集适合合并操作不适合拆分操作。如果题目要求“把某个元素从集合 A 移到集合 B”普通并查集做不到需要带删除标记的变体。做算法题之前一定先确认操作是只增不减还是可能有撤销。如果会有拆分别硬套并查集。我自己用并查集解决实际项目里的模块依赖分组时也遇到过类似情况。模块关系是静态的、只增不减用并查集写分组压缩非常顺手后来业务改成支持动态调整依赖我就不得不换成图数据库加拓扑排序那套方案。选数据结构和选工具一样先看清楚限制条件再决定要不要用。从 765 这道题出发把并查集的底层逻辑想通你就能体会到它的朴实与强大。不要满足于背一个公式建议你亲手画一画合并过程。拿 row [5, 4, 3, 2, 1, 0] 来模拟你会发现 union 的顺序不同路径压缩后的树结构也不同但最终 count 和答案是稳定的。这就是并查集的容错性关系怎么连它都只关心连通分量的数量。最后再分享一个我自己刷题时的习惯每道题动手前先在注释里写下三个词——节点、边、统计量。765 题的答案就是“节点是情侣对编号边是相邻非情侣关系统计量是 N 减连通分量数”。这个习惯帮我避开了无数因为建模错误导致的返工。希望这篇内容能让你重新认识并查集下一次再看到类似题目能直接看穿它的结构。