企业官网建设流程全解析

最近在力扣刷题，765题“情侣牵手”的题目标签里赫然写着 union-find，也就是并查集。很多朋友看到这题一脸懵：换座位跟并查集有什么关系？明明用贪心模拟交换也能做，为什么非要用一个听起来这么抽象的数据结构？其实这道题特别适合用来理解并查集的核心价值：它不关心你怎么一步一步交换，它只关心“这些坐错的人之间，构成了几个互相纠缠的团体”。搞懂这个，你就能直接写出答案公式：最少交换次数 = 情侣对数 - 并查集连通分量数。

这篇文章我会从并查集到底是干什么的开始讲，然后一步步推导力扣765的建模过程，把完整代码、底层的为什么、还有我实际提交时踩过的坑全部分享出来。适合刚接触并查集的算法新手，也适合准备面试想快速复习的人。

1. 先把并查集这东西的用途看明白

1.1 并查集到底在解决什么问题

并查集的全称是“不相交集合数据结构”，英文是 Disjoint Set Union，缩写为 DSU，也叫 union-find。它从名字上就写得很直白：union 是合并，find 是查找。所以它的核心任务只有两个，一是判断两个元素是否在同一个集合里，二是把两个集合合并成一个。

听起来很简单，但它的厉害之处在于“动态维护连通性”。什么叫动态？就是你不断地往系统里添加新的关系，比如告诉你 a 和 b 是朋友，又告诉你 b 和 c 是朋友，这时候你自然知道 a 和 c 也能扯上关系。随时有人问你“a 和 c 是朋友吗”，你都要能立刻回答。这种问题如果每次都用图遍历去搜，一次就是 O(N+M)，关系一多就完全扛不住。而并查集经过优化后，单次查询和合并的均摊复杂度趋近于 O(1)，这个性能差距在实际使用中非常明显。

并查集主要用来做什么的？一句话总结：处理一堆元素按照等价关系划分成若干个连通分量的问题。现实里的应用包括社交网络中的“朋友圈”划分、网络节点是否连通、Kruskal 算法求最小生成树、图片像素的连通区域标记、拼图游戏里碎片的分组等等。只要满足“两个东西之间存在一条关系链，并且关系可以传递”，大概率就能用并查集建模。

1.2 为什么“情侣牵手”会用到并查集

回到力扣 765。题目给了一个长度为 2n 的数组 row，row[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 依赖 find，find 依赖 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^1=1，1^1=0，2^1=3，3^1=2，4^1=5，5^1=4。这正好对应“相邻偶数和奇数是一对”的编号规则。用位运算判断情侣关系特别快，写起来也很优雅。

但我们建模时不直接用人的编号作为并查集节点，而是把第 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]，n=2。第一组座位是 0 和 2。0 的情侣应该是 1，不是 2，所以坐错。0//2=0，2//2=1，执行 union(0, 1)。第二组座位是 1 和 3。1 的情侣应该是 0，不是 3，所以坐错。1//2=0，3//2=1，再次 union(0, 1)。最后并查集只有 1 个连通分量，count=1，答案 = 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 -= 1

4.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 常见问题速查表

5. 从这道题延伸出去：并查集在真实场景中的价值

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 减连通分量数”。这个习惯帮我避开了无数因为建模错误导致的返工。希望这篇内容能让你重新认识并查集，下一次再看到类似题目，能直接看穿它的结构。