1. 初见765贪心能过但我被为什么正确问住了我刷并查集union-find专项题单时最先遇到的都是一批给一堆连接关系问连通块有几个的直白题目。直到碰见力扣765情侣牵手第一反应是这不是贪心模拟吗跟并查集有什么关系后来花了一个晚上把这道题彻底想透才发现它几乎是把并查集为什么能统计最小交换次数这个问题的答案掰开揉碎地写进了题目里。这篇文章不打算只贴一份AC代码而是把我从贪心到并查集、再到公式n - 连通分量数的完整思考链路整理出来适合正在刷并查集、或者被这道题的直觉解法困惑过的朋友。1.1 题目到底在问什么先把题意说清楚。n 对情侣编号规则是第0对是 (0,1)第1对是 (2,3)第2对是 (4,5)以此类推。他们随机坐在一排连续的 2n 个座位上一次操作可以随便拉两个人站起来交换座位。目标让每对情侣都坐在相邻的两个位置上。注意 (0,1) 和 (1,0) 都算正确只要他们挨着就行谁在左谁在右无所谓。举例来说row [0, 2, 1, 3] 表示0号人在位置02号人在位置11号人在位置23号人在位置3。0和1是一对2和3是一对但现在0挨着21挨着3谁都没挨着自己的伴侣。要让他们都牵手只需要交换一次把位置1的2和位置2的1换一下得到 [0,1,2,3]。答案就是1。row [3,2,0,1] 则不需要交换因为位置0的3和位置1的2恰好是第1对情侣位置2的0和位置3的1恰好是第0对情侣虽然整体顺序颠倒了但每对都挨着答案是0。这道题的难点在于n 最大可以到30所以暴力枚举所有交换方案是不可能完成的。大多数人的第一反应是做贪心我也是这么过来的但贪心之后紧接着就会遇到一个绕不开的问题为什么局部最优的交换一定能凑出全局最优1.2 贪心能过但疑点在哪我第一次写贪心非常直接用一个 pos 数组记录每个人当前坐在哪个位置从左往右扫描每两个座位一组如果 row[i] 和 row[i1] 恰好是一对就跳过否则找到 row[i] 伴侣的位置 j把 row[i1] 和 row[j] 交换同时更新 pos答案加一。代码挺短一次就AC了我也没多想就划走了。结果过了几天有个朋友拿同一道题来问我你这个贪心的正确性怎么证明我一开始想当然地说这不是显然吗从左到右处理每次把当前组弄对后面又不影响。但仔细一想不对交换 row[i1] 和 row[j] 的时候row[j] 会被换到 i1 这个位置它本来待在后面某个位置上你这么一换会不会把后面已经处理过的某组又弄乱了严格想一遍之后会发现它的安全性确实成立因为是从左往右处理row[i] 的伴侣被换到 i1 后当前组就正确了而被换走的 row[i1] 落到 j 位置这个 j 一定在当前组之后属于还没处理的后半段后面轮到那个座位组时自然会收拾它。所以贪心给出的确实是一个可行解。但可行不等于最优。万一有时候故意不在当前这一组上做交换先处理别的地方反而能省下次数呢这个问题用贪心自己的语言很难回答清楚只能靠枚举特例去碰运气验证。真正让我彻底放心的是换成并查集的视角重新看这道题。2. 并查集的三件小事find、union、还有那个接近O(1)的复杂度在回到765之前先把并查集这个工具本身磨清楚。很多人对并查集的印象停留在背模板但刷题和面试时真正容易翻车的恰恰是模板背后的几个细节。2.1 find 到底在找什么并查集维护的是一组不相交的集合每个集合选出一个代表元素叫根。两个元素在同一个集合里当且仅当它们的根相同。用数组 parent 表示一开始 parent[i] i意思是每个人都单独是一棵树。find(x) 的任务就是顺着 parent 一路往上爬找到 x 所在树的根。这里面的核心是代表元思想。打个比方每个群有一个群主成员之间不一定互相认识但你想知道两个人是不是同一个群只需要分别问出他们各自的群主是谁看是不是同一个人即可。如果群主相同不管中间隔了多少层他们一定在同一个圈子里。这个思想贯穿了几乎所有并查集题目我们需要的不是一个具体的排列顺序而是一个归属关系。2.2 路径压缩到底压缩了什么如果 find 每次都从头爬到根在极端情况下比如一字长蛇阵1 指向22 指向33 指向4……查询会退化成 O(n)。路径压缩解决的就是这个问题既然我这次已经从 x 一路爬到根了那沿途经过的所有节点干脆直接把它们的 parent 改成根下次再查它们就不用重新爬了。写成递归就是那段经典代码def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]很多人担心递归会不会爆栈。实际上由于路径压缩的存在树的深度会在操作过程中快速缩小几十万甚至上百万的数据规模都不太可能碰到递归深度上限。真正要小心的反而是只背模板不理解如果你不理解self.parent[x] self.find(self.parent[x])这一行的作用一旦题目换成带权并查集路径压缩时还要同步维护权值你立刻就会懵。所以建议把这个递归过程在纸上画一棵三层的树手动走一遍比背着写十遍都管用。2.3 按秩合并和够用就好的取舍按秩合并union by rank是第二个优化合并两棵树时把矮的树接到高的树下面避免树越来越深。加上路径压缩后单次 find 或 union 的均摊复杂度是 O(α(n))其中 α 是反阿克曼函数你不需要关心它怎么算只需要知道一个事实对于任何现实规模的数据α(n) 不会超过5所以完全可以当常数 O(1) 看待。我在刷765的时候用的是完整版路径压缩和按秩合并都写了。但如果只做路径压缩不写 rank能不能过也能过因为题目规模很小路径压缩后性能已经足够。这里给个取舍建议如果你只是想快速AC简化版没问题但如果是在面试现场或者你打算长期刷并查集类题目建议把两个优化都写上。原因不是性能而是按秩合并让树高可控这件事变得可以论证面试官追问复杂度的时候你能更有底气地回答。2.4 模板一个带 count 的够用实现我平时使用的模板会多维护一个 count记录当前连通分量的个数。这个变量在很多题目里直接就是答案的一部分765就是典型例子。注意union 成功一次count 就减1如果两个节点本来就在同一个集合里count 不变。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 self.count - 1find 这个 while 版本用了一个常见的小优化隔代路径压缩。每跳一步就把 parent[x] 指向祖父节点虽然不是一步到底但能把树高砍掉一半代码比递归版更省心也不用担心栈深度。模板只是工具真正重要的是你想清楚它能帮你维护什么信息。3. 把座位关系翻译成图为什么答案等于 n 减去连通分量数回到765。并查集解法的思路可以拆成三步编号、连边、数块。3.1 编号把每个人映射到第几对情侣情侣编号的规则是第 i 对情侣由 2i 和 2i1 两个人组成。所以一个人编号是 x它属于第 x//2 对。这个映射简单到容易让人忽略但它是整个解法的第一块基石。举例4 属于第2对4//227 属于第3对7//23。所有人和座位对的映射关系都用整数除法完成。3.2 连边每个座位组是一个证据把 2n 个座位分成 n 个座位组第0组是位置0和1第1组是位置2和3第2组是位置4和5以此类推。逐个检查组内两个人分别属于第几对情侣记为 a 和 b。如果 a 等于 b说明这对情侣已经正确落在同一个座位组里不需要处理如果 a 不等于 b说明第 a 对情侣和第 b 对情侣之间发生了串位就在 a 和 b 之间连一条无向边。这条边记录了一个事实第 a 对情侣中的人没有坐在第 a 组座位上而是出现在第 b 组座位上。顺着这些边走下去你会得到若干个环。比如示例 [0,2,1,3]座位组0坐着0号人第0对和2号人第1对连边0-1座位组1坐着1号人第0对和3号人第1对又连一条0-1边。两条边构成了一个二环直观听起来就是第0对和第1对互换了座位区域。3.3 数块答案就是 n - uf.count并查集把所有边合并完毕后统计连通分量个数。每个连通分量里的节点数减1就是理顺这个分量内部需要的最少交换次数。把所有分量求和总交换次数 Σ(size_i - 1) (Σ size_i) - 连通分量个数 n - 连通分量个数这里的 n 是情侣对数也就是并查集的节点数。为什么每个连通分量需要 size-1 次因为一个分量为 size 的错位结构本质上是一个置换环。最小的环是两对情侣互相坐错交换一次就能全部归位三对情侣互相错位需要交换两次。每多一对就多需要一次交换。把每个环需要的 size-1 加在一起就得到了上面的统一公式。更严谨一点还可以做一个上下界论证。下界一次交换操作在并查集图上最多只能让连通分量个数增加1因为一次操作只涉及两个座位上的两个人受影响的连通分量最多从一个变成两个不可能一个变成三个。最终全部正确时每个节点单独成块分量数从 c 变成 n因此至少需要 n-c 次交换。上界对每个环按从左到右的顺序执行交换恰好能用 size-1 次把环完全拆开总次数正好是 n-c。上下界相等所以答案精确等于 n 减连通分量数。3.4 两个手算的例子加深直觉先看 [0,2,1,3]。情侣编号序列座位组0里是 (0,1)即第0对和第1对连边0-1座位组1里是 (0,1)又是第0对和第1对再连边0-1。并查集最终只有1个连通分量答案 2-1 1。再看 row [3,2,0,1]座位组0里是 (1,1)因为3//21、2//21自环座位组1里是 (0,0)也是自环。两个连通分量答案 2-2 0。这和手动观察一致3和2挨着0和1挨着已经全部正确。最后看一个三对的例子[2,0,5,4,3,1]。座位组0是2号人和0号人属于第1对和第0对连边0-1座位组1是5号人和4号人属于第2对和第2对自环座位组2是3号人和1号人属于第1对和第0对又连边0-1。最终连通分量只有两个{0,1} 和 {2}答案 3-2 1。手动交换一次也确实能到位说明公式没有骗人。4. 贪心解法与并查集解法的统一原来都在拆环搞懂了并查集解法之后再回头看贪心就会发现两者根本是同一件事。贪心的每一次交换都是在并查集图上剪掉一条边让一个环裂成两个更小的环等所有环都拆成自环一切也就归位了。4.1 贪心代码与它的执行轨迹贪心解法不依赖并查集代码反而更贴近模拟的直觉def minSwapsCouples(row): n len(row) pos [0] * n for i, x in enumerate(row): pos[x] i ans 0 for i in range(0, n, 2): x row[i] partner x ^ 1 if row[i 1] partner: continue j pos[partner] row[i 1], row[j] row[j], row[i 1] pos[row[i 1]] i 1 pos[row[j]] j ans 1 return ans这里有个值得记住的小技巧找伴侣编号用位运算x ^ 1因为偶数和1异或得到下一个奇数奇数和1异或得到上一个偶数。比如 6^17、7^16。这比写 if-else 判断奇偶要简洁得多而且不容易出错。如果你从未用过这个技巧建议在纸上验证几个数它其实是二进制的性质最低位翻转。4.2 为什么每次把当前组弄对恰好达到最优现在回答当初那个把我问住的问题为什么贪心的局部最优等于全局最优关键观察是每一次成功交换都会让并查集里的连通分量个数恰好增加1。举例来说当贪心发现位置 i 上的 row[i] 没挨着伴侣时它会把 row[i] 的伴侣从位置 j 换到 i1 来。在并查集图上这相当于把第 a 对和第 b 对之间的那条错位边拆掉同时让第 a 对成为自环。原本一个包含 a 和 b 的环就此分裂成一个自环加一个更小的环连通分量数加1。而下界分析已经说明了任何一次交换最多只能让分量数加1。贪心每一步都踩在这个上限上所以它不会浪费任何一次操作。于是贪心执行 n - 连通分量数 步后所有分量变成 n 个自环节点任务完成。这就是贪心正确性的完整证明它本质上是在说贪心是拆环过程的一种具体实现而拆环所需的最小步数由环的数量唯一决定。4.3 两种解法的对比维度贪心解法并查集解法核心操作模拟交换维护 pos 数组建图 统计连通分量时间复杂度O(n)O(n α(n))空间复杂度O(n)O(n)是否真的交换是否证明难度需要拆环论证公式推导更直观代码量稍长更短如果只是为了AC这道题贪心是更快的路径如果是为了理解为什么最少交换次数可以用连通性来度量并查集解法是不可替代的。站在刷题的角度我建议你把两种都写一遍再对照着看一遍。5. 完整实现与提交时会踩的坑到了上代码的环节。以下版本可以直接提交我在 LeetCode 环境里实测过。5.1 可直接提交的完整代码from typing import List class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 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 uf.union(a, b) return n - uf.count注意并查集的节点数是情侣对数 n而不是座位数 2n。这个细节一旦搞错后面的连通分量计数就全乱了。循环里每处理一个座位组就做一次 union所有错位关系都合并进去最后用n - uf.count一算答案就出来了。5.2 坑1别把情侣编号和伴侣编号搞混row[i] // 2得到的是第几对情侣而row[i] ^ 1得到的是伴侣本人。并查集解法只需要前者贪心解法才需要后者。如果在并查集代码里误用了^1比如判断 a 和 b 是否相等时使用了row[i] ^ 1 row[i1]就会把这两个人是不是恰好挨着的伴侣混进并查集的节点里导致节点编号变成人的编号而不是情侣对编号最后全盘皆输。5.3 坑2自环不会影响答案但可以顺手优化当 a 等于 b 时说明这个座位组已经正确。union 内部会先 find 两次发现根相同然后直接 returncount 不变。所以不显式跳过自环代码也是对的。如果数据量很大可以在循环里加一句if a ! b: uf.union(a, b)省掉两次 find 调用。765 的数据规模很小不优化也能过但养成这个习惯对后面刷其他并查集变体题有好处。5.4 坑3递归 find 和迭代 find 怎么选递归版代码最简洁self.parent[x] self.find(self.parent[x])一行就把路径压缩做完了。但 Python 默认递归深度大约1000层虽然路径压缩能保证树的深度通常很小万一遇到某些极端构造先建一棵超长链再一次次触发 find还是有可能撞上递归上限。因此我更推荐使用 while 迭代版也就是模板里的隔代路径压缩写法。它不依赖调用栈而且在大部分场景下性能表现已经足够稳定。5.5 值得自测的边界用例row [0, 1, 2, 3]答案0本来就全对。row [0, 2, 1, 3]答案1经典的二环。row [3, 2, 0, 1]答案0整体倒序但相邻关系正确。row [1, 0, 3, 2]答案0注意情侣不要求固定左右顺序。n 1时row [0, 1]或row [1, 0]答案都是0。[1, 0, 3, 2]这个用例特别容易坑人因为看起来0 和 1 没按大小顺序排但实际上 1 和 0 挨着坐就已经是牵手成功了题目从不要求编号从小到大排列。6. 从765往外走一步带权并查集和同族题目765 只用到了并查集最朴素的连通性语义。但并查集家族里还有一个重要分支带权并查集。它会在每条父子关系上附带一个数值用来表示子节点到父节点的某种差值或方向常见的应用包括食物链的吃与被吃关系、奇偶区间的判断、战舰队列的间隔距离等等。6.1 带权并查集到底在维护什么普通并查集只回答x 和 y 在不在同一个集合带权并查集还能回答x 相对根的关系值是多少。实现时除了 parent 数组外再维护一个 weight 数组表示当前节点到父节点的权值。路径压缩时需要同步把沿途的权值累加起来union 时要根据题目语义选择合适的边权赋值公式。这里有一个非常容易写错的地方find 递归返回前必须先累加旧父节点的权值再更新 parent顺序不能反。一个示意性的写法如下class WeightedUnionFind: def __init__(self, n): self.parent list(range(n)) self.weight [0] * n def find(self, x): if self.parent[x] ! x: root self.find(self.parent[x]) self.weight[x] self.weight[self.parent[x]] self.parent[x] root return self.parent[x]注意这里的权值语义完全由题目决定不是一套公式走天下的。765 本身不需要带权因为它只关心连通性不关心偏移了几对但如果你在题单里看到带权并查集几个字不要慌它只是在普通并查集的骨架上多维护了一个计数器。6.2 同族题目从数连通块到算最少操作这类把关系抽象成连边再用并查集统计连通块的题目在力扣上有好几个长相不同但内核一致的兄弟力扣1319. 连通网络的操作次数n 台计算机和若干连接求让整张图连通的最少操作次数。如果连接数不足返回-1否则答案是连通分量数减1。力扣684. 冗余连接给一棵树多加了一条边找出这条边。并查集在加边过程中如果发现两个端点已经连通当前边就是那条冗余边。力扣547. 省份数量直接数连通分量个数。力扣1202. 交换字符串中的元素下标之间可以互换问能得到的最小字典序字符串。本质是把可交换的下标并成连通块在块内排序。力扣947. 移除最多的同行或同列石头把同行同列的石头并到同一集合答案是石头总数减去连通块数。这些题有一个共同点先想清楚把什么看成节点、把什么看成边再用并查集把对象聚成若干连通块最后答案通常和连通块的数量或大小有关。看得多了你会发现并查集做题真正的难点从来不在模板代码而在于建图建模的思路。6.3 我的练习建议我自己刷并查集的一个笨办法是每道题都用相同的问题逼问自己三遍——我建的点是什么我建的边是什么答案为什么要用连通分量数来表达765 特别适合当这三连问的入门题因为它的答案表达式n - 分量数摆得明明白白。等你想通这三问再去看带权并查集、离散化、离线查询这些进阶内容就会发现它们并不是什么全新知识只是在同一个骨架上加了不同的肉。最后分享一个写这类题的小习惯我会在并查集里用 count 变量实时记录连通分量数这样比最后再遍历一遍 parent 数根要快而且直观。它只受 union 成功与否影响和树的形态没有任何关系所以无论你用不用按秩合并count 的值都是可靠的。这个细节在笔试的紧张环境下很容易被忽略但提前确认清楚能省掉后面一大段调试时间。
1. 初见765贪心能过但我被为什么正确问住了我刷并查集union-find专项题单时最先遇到的都是一批给一堆连接关系问连通块有几个的直白题目。直到碰见力扣765情侣牵手第一反应是这不是贪心模拟吗跟并查集有什么关系后来花了一个晚上把这道题彻底想透才发现它几乎是把并查集为什么能统计最小交换次数这个问题的答案掰开揉碎地写进了题目里。这篇文章不打算只贴一份AC代码而是把我从贪心到并查集、再到公式n - 连通分量数的完整思考链路整理出来适合正在刷并查集、或者被这道题的直觉解法困惑过的朋友。1.1 题目到底在问什么先把题意说清楚。n 对情侣编号规则是第0对是 (0,1)第1对是 (2,3)第2对是 (4,5)以此类推。他们随机坐在一排连续的 2n 个座位上一次操作可以随便拉两个人站起来交换座位。目标让每对情侣都坐在相邻的两个位置上。注意 (0,1) 和 (1,0) 都算正确只要他们挨着就行谁在左谁在右无所谓。举例来说row [0, 2, 1, 3] 表示0号人在位置02号人在位置11号人在位置23号人在位置3。0和1是一对2和3是一对但现在0挨着21挨着3谁都没挨着自己的伴侣。要让他们都牵手只需要交换一次把位置1的2和位置2的1换一下得到 [0,1,2,3]。答案就是1。row [3,2,0,1] 则不需要交换因为位置0的3和位置1的2恰好是第1对情侣位置2的0和位置3的1恰好是第0对情侣虽然整体顺序颠倒了但每对都挨着答案是0。这道题的难点在于n 最大可以到30所以暴力枚举所有交换方案是不可能完成的。大多数人的第一反应是做贪心我也是这么过来的但贪心之后紧接着就会遇到一个绕不开的问题为什么局部最优的交换一定能凑出全局最优1.2 贪心能过但疑点在哪我第一次写贪心非常直接用一个 pos 数组记录每个人当前坐在哪个位置从左往右扫描每两个座位一组如果 row[i] 和 row[i1] 恰好是一对就跳过否则找到 row[i] 伴侣的位置 j把 row[i1] 和 row[j] 交换同时更新 pos答案加一。代码挺短一次就AC了我也没多想就划走了。结果过了几天有个朋友拿同一道题来问我你这个贪心的正确性怎么证明我一开始想当然地说这不是显然吗从左到右处理每次把当前组弄对后面又不影响。但仔细一想不对交换 row[i1] 和 row[j] 的时候row[j] 会被换到 i1 这个位置它本来待在后面某个位置上你这么一换会不会把后面已经处理过的某组又弄乱了严格想一遍之后会发现它的安全性确实成立因为是从左往右处理row[i] 的伴侣被换到 i1 后当前组就正确了而被换走的 row[i1] 落到 j 位置这个 j 一定在当前组之后属于还没处理的后半段后面轮到那个座位组时自然会收拾它。所以贪心给出的确实是一个可行解。但可行不等于最优。万一有时候故意不在当前这一组上做交换先处理别的地方反而能省下次数呢这个问题用贪心自己的语言很难回答清楚只能靠枚举特例去碰运气验证。真正让我彻底放心的是换成并查集的视角重新看这道题。2. 并查集的三件小事find、union、还有那个接近O(1)的复杂度在回到765之前先把并查集这个工具本身磨清楚。很多人对并查集的印象停留在背模板但刷题和面试时真正容易翻车的恰恰是模板背后的几个细节。2.1 find 到底在找什么并查集维护的是一组不相交的集合每个集合选出一个代表元素叫根。两个元素在同一个集合里当且仅当它们的根相同。用数组 parent 表示一开始 parent[i] i意思是每个人都单独是一棵树。find(x) 的任务就是顺着 parent 一路往上爬找到 x 所在树的根。这里面的核心是代表元思想。打个比方每个群有一个群主成员之间不一定互相认识但你想知道两个人是不是同一个群只需要分别问出他们各自的群主是谁看是不是同一个人即可。如果群主相同不管中间隔了多少层他们一定在同一个圈子里。这个思想贯穿了几乎所有并查集题目我们需要的不是一个具体的排列顺序而是一个归属关系。2.2 路径压缩到底压缩了什么如果 find 每次都从头爬到根在极端情况下比如一字长蛇阵1 指向22 指向33 指向4……查询会退化成 O(n)。路径压缩解决的就是这个问题既然我这次已经从 x 一路爬到根了那沿途经过的所有节点干脆直接把它们的 parent 改成根下次再查它们就不用重新爬了。写成递归就是那段经典代码def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]很多人担心递归会不会爆栈。实际上由于路径压缩的存在树的深度会在操作过程中快速缩小几十万甚至上百万的数据规模都不太可能碰到递归深度上限。真正要小心的反而是只背模板不理解如果你不理解self.parent[x] self.find(self.parent[x])这一行的作用一旦题目换成带权并查集路径压缩时还要同步维护权值你立刻就会懵。所以建议把这个递归过程在纸上画一棵三层的树手动走一遍比背着写十遍都管用。2.3 按秩合并和够用就好的取舍按秩合并union by rank是第二个优化合并两棵树时把矮的树接到高的树下面避免树越来越深。加上路径压缩后单次 find 或 union 的均摊复杂度是 O(α(n))其中 α 是反阿克曼函数你不需要关心它怎么算只需要知道一个事实对于任何现实规模的数据α(n) 不会超过5所以完全可以当常数 O(1) 看待。我在刷765的时候用的是完整版路径压缩和按秩合并都写了。但如果只做路径压缩不写 rank能不能过也能过因为题目规模很小路径压缩后性能已经足够。这里给个取舍建议如果你只是想快速AC简化版没问题但如果是在面试现场或者你打算长期刷并查集类题目建议把两个优化都写上。原因不是性能而是按秩合并让树高可控这件事变得可以论证面试官追问复杂度的时候你能更有底气地回答。2.4 模板一个带 count 的够用实现我平时使用的模板会多维护一个 count记录当前连通分量的个数。这个变量在很多题目里直接就是答案的一部分765就是典型例子。注意union 成功一次count 就减1如果两个节点本来就在同一个集合里count 不变。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 self.count - 1find 这个 while 版本用了一个常见的小优化隔代路径压缩。每跳一步就把 parent[x] 指向祖父节点虽然不是一步到底但能把树高砍掉一半代码比递归版更省心也不用担心栈深度。模板只是工具真正重要的是你想清楚它能帮你维护什么信息。3. 把座位关系翻译成图为什么答案等于 n 减去连通分量数回到765。并查集解法的思路可以拆成三步编号、连边、数块。3.1 编号把每个人映射到第几对情侣情侣编号的规则是第 i 对情侣由 2i 和 2i1 两个人组成。所以一个人编号是 x它属于第 x//2 对。这个映射简单到容易让人忽略但它是整个解法的第一块基石。举例4 属于第2对4//227 属于第3对7//23。所有人和座位对的映射关系都用整数除法完成。3.2 连边每个座位组是一个证据把 2n 个座位分成 n 个座位组第0组是位置0和1第1组是位置2和3第2组是位置4和5以此类推。逐个检查组内两个人分别属于第几对情侣记为 a 和 b。如果 a 等于 b说明这对情侣已经正确落在同一个座位组里不需要处理如果 a 不等于 b说明第 a 对情侣和第 b 对情侣之间发生了串位就在 a 和 b 之间连一条无向边。这条边记录了一个事实第 a 对情侣中的人没有坐在第 a 组座位上而是出现在第 b 组座位上。顺着这些边走下去你会得到若干个环。比如示例 [0,2,1,3]座位组0坐着0号人第0对和2号人第1对连边0-1座位组1坐着1号人第0对和3号人第1对又连一条0-1边。两条边构成了一个二环直观听起来就是第0对和第1对互换了座位区域。3.3 数块答案就是 n - uf.count并查集把所有边合并完毕后统计连通分量个数。每个连通分量里的节点数减1就是理顺这个分量内部需要的最少交换次数。把所有分量求和总交换次数 Σ(size_i - 1) (Σ size_i) - 连通分量个数 n - 连通分量个数这里的 n 是情侣对数也就是并查集的节点数。为什么每个连通分量需要 size-1 次因为一个分量为 size 的错位结构本质上是一个置换环。最小的环是两对情侣互相坐错交换一次就能全部归位三对情侣互相错位需要交换两次。每多一对就多需要一次交换。把每个环需要的 size-1 加在一起就得到了上面的统一公式。更严谨一点还可以做一个上下界论证。下界一次交换操作在并查集图上最多只能让连通分量个数增加1因为一次操作只涉及两个座位上的两个人受影响的连通分量最多从一个变成两个不可能一个变成三个。最终全部正确时每个节点单独成块分量数从 c 变成 n因此至少需要 n-c 次交换。上界对每个环按从左到右的顺序执行交换恰好能用 size-1 次把环完全拆开总次数正好是 n-c。上下界相等所以答案精确等于 n 减连通分量数。3.4 两个手算的例子加深直觉先看 [0,2,1,3]。情侣编号序列座位组0里是 (0,1)即第0对和第1对连边0-1座位组1里是 (0,1)又是第0对和第1对再连边0-1。并查集最终只有1个连通分量答案 2-1 1。再看 row [3,2,0,1]座位组0里是 (1,1)因为3//21、2//21自环座位组1里是 (0,0)也是自环。两个连通分量答案 2-2 0。这和手动观察一致3和2挨着0和1挨着已经全部正确。最后看一个三对的例子[2,0,5,4,3,1]。座位组0是2号人和0号人属于第1对和第0对连边0-1座位组1是5号人和4号人属于第2对和第2对自环座位组2是3号人和1号人属于第1对和第0对又连边0-1。最终连通分量只有两个{0,1} 和 {2}答案 3-2 1。手动交换一次也确实能到位说明公式没有骗人。4. 贪心解法与并查集解法的统一原来都在拆环搞懂了并查集解法之后再回头看贪心就会发现两者根本是同一件事。贪心的每一次交换都是在并查集图上剪掉一条边让一个环裂成两个更小的环等所有环都拆成自环一切也就归位了。4.1 贪心代码与它的执行轨迹贪心解法不依赖并查集代码反而更贴近模拟的直觉def minSwapsCouples(row): n len(row) pos [0] * n for i, x in enumerate(row): pos[x] i ans 0 for i in range(0, n, 2): x row[i] partner x ^ 1 if row[i 1] partner: continue j pos[partner] row[i 1], row[j] row[j], row[i 1] pos[row[i 1]] i 1 pos[row[j]] j ans 1 return ans这里有个值得记住的小技巧找伴侣编号用位运算x ^ 1因为偶数和1异或得到下一个奇数奇数和1异或得到上一个偶数。比如 6^17、7^16。这比写 if-else 判断奇偶要简洁得多而且不容易出错。如果你从未用过这个技巧建议在纸上验证几个数它其实是二进制的性质最低位翻转。4.2 为什么每次把当前组弄对恰好达到最优现在回答当初那个把我问住的问题为什么贪心的局部最优等于全局最优关键观察是每一次成功交换都会让并查集里的连通分量个数恰好增加1。举例来说当贪心发现位置 i 上的 row[i] 没挨着伴侣时它会把 row[i] 的伴侣从位置 j 换到 i1 来。在并查集图上这相当于把第 a 对和第 b 对之间的那条错位边拆掉同时让第 a 对成为自环。原本一个包含 a 和 b 的环就此分裂成一个自环加一个更小的环连通分量数加1。而下界分析已经说明了任何一次交换最多只能让分量数加1。贪心每一步都踩在这个上限上所以它不会浪费任何一次操作。于是贪心执行 n - 连通分量数 步后所有分量变成 n 个自环节点任务完成。这就是贪心正确性的完整证明它本质上是在说贪心是拆环过程的一种具体实现而拆环所需的最小步数由环的数量唯一决定。4.3 两种解法的对比维度贪心解法并查集解法核心操作模拟交换维护 pos 数组建图 统计连通分量时间复杂度O(n)O(n α(n))空间复杂度O(n)O(n)是否真的交换是否证明难度需要拆环论证公式推导更直观代码量稍长更短如果只是为了AC这道题贪心是更快的路径如果是为了理解为什么最少交换次数可以用连通性来度量并查集解法是不可替代的。站在刷题的角度我建议你把两种都写一遍再对照着看一遍。5. 完整实现与提交时会踩的坑到了上代码的环节。以下版本可以直接提交我在 LeetCode 环境里实测过。5.1 可直接提交的完整代码from typing import List class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 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 uf.union(a, b) return n - uf.count注意并查集的节点数是情侣对数 n而不是座位数 2n。这个细节一旦搞错后面的连通分量计数就全乱了。循环里每处理一个座位组就做一次 union所有错位关系都合并进去最后用n - uf.count一算答案就出来了。5.2 坑1别把情侣编号和伴侣编号搞混row[i] // 2得到的是第几对情侣而row[i] ^ 1得到的是伴侣本人。并查集解法只需要前者贪心解法才需要后者。如果在并查集代码里误用了^1比如判断 a 和 b 是否相等时使用了row[i] ^ 1 row[i1]就会把这两个人是不是恰好挨着的伴侣混进并查集的节点里导致节点编号变成人的编号而不是情侣对编号最后全盘皆输。5.3 坑2自环不会影响答案但可以顺手优化当 a 等于 b 时说明这个座位组已经正确。union 内部会先 find 两次发现根相同然后直接 returncount 不变。所以不显式跳过自环代码也是对的。如果数据量很大可以在循环里加一句if a ! b: uf.union(a, b)省掉两次 find 调用。765 的数据规模很小不优化也能过但养成这个习惯对后面刷其他并查集变体题有好处。5.4 坑3递归 find 和迭代 find 怎么选递归版代码最简洁self.parent[x] self.find(self.parent[x])一行就把路径压缩做完了。但 Python 默认递归深度大约1000层虽然路径压缩能保证树的深度通常很小万一遇到某些极端构造先建一棵超长链再一次次触发 find还是有可能撞上递归上限。因此我更推荐使用 while 迭代版也就是模板里的隔代路径压缩写法。它不依赖调用栈而且在大部分场景下性能表现已经足够稳定。5.5 值得自测的边界用例row [0, 1, 2, 3]答案0本来就全对。row [0, 2, 1, 3]答案1经典的二环。row [3, 2, 0, 1]答案0整体倒序但相邻关系正确。row [1, 0, 3, 2]答案0注意情侣不要求固定左右顺序。n 1时row [0, 1]或row [1, 0]答案都是0。[1, 0, 3, 2]这个用例特别容易坑人因为看起来0 和 1 没按大小顺序排但实际上 1 和 0 挨着坐就已经是牵手成功了题目从不要求编号从小到大排列。6. 从765往外走一步带权并查集和同族题目765 只用到了并查集最朴素的连通性语义。但并查集家族里还有一个重要分支带权并查集。它会在每条父子关系上附带一个数值用来表示子节点到父节点的某种差值或方向常见的应用包括食物链的吃与被吃关系、奇偶区间的判断、战舰队列的间隔距离等等。6.1 带权并查集到底在维护什么普通并查集只回答x 和 y 在不在同一个集合带权并查集还能回答x 相对根的关系值是多少。实现时除了 parent 数组外再维护一个 weight 数组表示当前节点到父节点的权值。路径压缩时需要同步把沿途的权值累加起来union 时要根据题目语义选择合适的边权赋值公式。这里有一个非常容易写错的地方find 递归返回前必须先累加旧父节点的权值再更新 parent顺序不能反。一个示意性的写法如下class WeightedUnionFind: def __init__(self, n): self.parent list(range(n)) self.weight [0] * n def find(self, x): if self.parent[x] ! x: root self.find(self.parent[x]) self.weight[x] self.weight[self.parent[x]] self.parent[x] root return self.parent[x]注意这里的权值语义完全由题目决定不是一套公式走天下的。765 本身不需要带权因为它只关心连通性不关心偏移了几对但如果你在题单里看到带权并查集几个字不要慌它只是在普通并查集的骨架上多维护了一个计数器。6.2 同族题目从数连通块到算最少操作这类把关系抽象成连边再用并查集统计连通块的题目在力扣上有好几个长相不同但内核一致的兄弟力扣1319. 连通网络的操作次数n 台计算机和若干连接求让整张图连通的最少操作次数。如果连接数不足返回-1否则答案是连通分量数减1。力扣684. 冗余连接给一棵树多加了一条边找出这条边。并查集在加边过程中如果发现两个端点已经连通当前边就是那条冗余边。力扣547. 省份数量直接数连通分量个数。力扣1202. 交换字符串中的元素下标之间可以互换问能得到的最小字典序字符串。本质是把可交换的下标并成连通块在块内排序。力扣947. 移除最多的同行或同列石头把同行同列的石头并到同一集合答案是石头总数减去连通块数。这些题有一个共同点先想清楚把什么看成节点、把什么看成边再用并查集把对象聚成若干连通块最后答案通常和连通块的数量或大小有关。看得多了你会发现并查集做题真正的难点从来不在模板代码而在于建图建模的思路。6.3 我的练习建议我自己刷并查集的一个笨办法是每道题都用相同的问题逼问自己三遍——我建的点是什么我建的边是什么答案为什么要用连通分量数来表达765 特别适合当这三连问的入门题因为它的答案表达式n - 分量数摆得明明白白。等你想通这三问再去看带权并查集、离散化、离线查询这些进阶内容就会发现它们并不是什么全新知识只是在同一个骨架上加了不同的肉。最后分享一个写这类题的小习惯我会在并查集里用 count 变量实时记录连通分量数这样比最后再遍历一遍 parent 数根要快而且直观。它只受 union 成功与否影响和树的形态没有任何关系所以无论你用不用按秩合并count 的值都是可靠的。这个细节在笔试的紧张环境下很容易被忽略但提前确认清楚能省掉后面一大段调试时间。
