企业官网建设流程全解析

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号人在位置0，2号人在位置1，1号人在位置2，3号人在位置3。0和1是一对，2和3是一对，但现在0挨着2，1挨着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[i+1] 恰好是一对，就跳过；否则找到 row[i] 伴侣的位置 j，把 row[i+1] 和 row[j] 交换，同时更新 pos，答案加一。代码挺短，一次就AC了，我也没多想就划走了。

结果过了几天，有个朋友拿同一道题来问我："你这个贪心的正确性怎么证明？"我一开始想当然地说："这不是显然吗？从左到右处理，每次把当前组弄对，后面又不影响。"但仔细一想不对：交换 row[i+1] 和 row[j] 的时候，row[j] 会被换到 i+1 这个位置，它本来待在后面某个位置上，你这么一换，会不会把后面已经处理过的某组又弄乱了？

严格想一遍之后会发现，它的安全性确实成立：因为是从左往右处理，row[i] 的伴侣被换到 i+1 后，当前组就正确了；而被换走的 row[i+1] 落到 j 位置，这个 j 一定在当前组之后，属于"还没处理的后半段"，后面轮到那个座位组时自然会收拾它。所以贪心给出的确实是一个可行解。但"可行"不等于"最优"。万一有时候故意不在当前这一组上做交换，先处理别的地方，反而能省下次数呢？这个问题用贪心自己的语言很难回答清楚，只能靠枚举特例去碰运气验证。真正让我彻底放心的，是换成并查集的视角重新看这道题。

2. 并查集的三件小事：find、union、还有那个接近O(1)的复杂度

在回到765之前，先把并查集这个工具本身磨清楚。很多人对并查集的印象停留在"背模板"，但刷题和面试时真正容易翻车的，恰恰是模板背后的几个细节。

2.1 find 到底在找什么

并查集维护的是一组不相交的集合，每个集合选出一个代表元素，叫根。两个元素在同一个集合里，当且仅当它们的根相同。用数组 parent 表示：一开始 parent[i] = i，意思是每个人都单独是一棵树。find(x) 的任务就是顺着 parent 一路往上爬，找到 x 所在树的根。

这里面的核心是"代表元"思想。打个比方，每个群有一个群主，成员之间不一定互相认识，但你想知道两个人是不是同一个群，只需要分别问出他们各自的群主是谁，看是不是同一个人即可。如果群主相同，不管中间隔了多少层，他们一定在同一个圈子里。这个思想贯穿了几乎所有并查集题目：我们需要的不是一个具体的排列顺序，而是一个"归属关系"。

2.2 路径压缩到底压缩了什么

如果 find 每次都从头爬到根，在极端情况下（比如一字长蛇阵：1 指向2，2 指向3，3 指向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 -= 1

find 这个 while 版本用了一个常见的小优化：隔代路径压缩。每跳一步就把 parent[x] 指向祖父节点，虽然不是一步到底，但能把树高砍掉一半，代码比递归版更省心，也不用担心栈深度。模板只是工具，真正重要的是你想清楚它能帮你维护什么信息。

3. 把座位关系翻译成图：为什么答案等于 n 减去连通分量数

回到765。并查集解法的思路可以拆成三步：编号、连边、数块。

3.1 编号：把每个人映射到"第几对情侣"

情侣编号的规则是：第 i 对情侣由 2i 和 2i+1 两个人组成。所以一个人编号是 x，它属于第 x//2 对。这个映射简单到容易让人忽略，但它是整个解法的第一块基石。举例：4 属于第2对（4//2=2），7 属于第3对（7//2=3）。所有人和座位对的映射关系都用整数除法完成。

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//2=1、2//2=1，自环；座位组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^1=7、7^1=6。这比写 if-else 判断奇偶要简洁得多，而且不容易出错。如果你从未用过这个技巧，建议在纸上验证几个数，它其实是二进制的性质：最低位翻转。

4.2 为什么"每次把当前组弄对"恰好达到最优

现在回答当初那个把我问住的问题：为什么贪心的局部最优等于全局最优？

关键观察是：每一次成功交换，都会让并查集里的连通分量个数恰好增加1。举例来说，当贪心发现位置 i 上的 row[i] 没挨着伴侣时，它会把 row[i] 的伴侣从位置 j 换到 i+1 来。在并查集图上，这相当于把第 a 对和第 b 对之间的那条错位边拆掉，同时让第 a 对成为自环。原本一个包含 a 和 b 的环，就此分裂成一个自环加一个更小的环，连通分量数加1。

而下界分析已经说明了：任何一次交换最多只能让分量数加1。贪心每一步都踩在这个上限上，所以它不会浪费任何一次操作。于是贪心执行 n - 连通分量数 步后，所有分量变成 n 个自环节点，任务完成。这就是"贪心正确性"的完整证明，它本质上是在说：贪心是拆环过程的一种具体实现，而拆环所需的最小步数由环的数量唯一决定。

4.3 两种解法的对比

如果只是为了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[i+1]，就会把"这两个人是不是恰好挨着的伴侣"混进并查集的节点里，导致节点编号变成人的编号而不是情侣对编号，最后全盘皆输。

5.3 坑2：自环不会影响答案，但可以顺手优化

当 a 等于 b 时，说明这个座位组已经正确。union 内部会先 find 两次，发现根相同，然后直接 return，count 不变。所以不显式跳过自环，代码也是对的。如果数据量很大，可以在循环里加一句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 的值都是可靠的。这个细节在笔试的紧张环境下很容易被忽略，但提前确认清楚，能省掉后面一大段调试时间。