企业官网建设流程全解析

你大概率在“数据结构”相关的章节里见过它：并查集，英文叫 Disjoint Set Union，简称 DSU。我第一次认真吃透它，不是在上课，而是在一场笔试里被一道“动态加边判断连通”的题恶心到之后。当时我只会DFS染色，每加一条边就重扫一遍图，结果数据一到 10 万级别就直接超时。后来才明白，如果问题只关心“两个元素在不在同一个集合”，不关心它们之间的路径长什么样，并查集就是最优解之一。这篇文章适合正在学数据结构的人、准备考研或面试的人，以及工作中和连通性、等价类问题打交道的工程师。我会从最笨的写法一路讲到带权并查集的偏移量公式，顺带把工程里容易踩的坑也一起说了。

1. 先搞清楚：并查集到底在解决哪一类问题

1.1 一个真实场景：朋友圈的圈子

假设一个社交平台有 n 个用户，平台给你 m 条“互相关注”的关系，问你最终有多少个互不连通的圈子。如果你用图的 DFS/BFS，每次来一条新关系，可能要重新遍历一次图，复杂度直接裂开。而并查集的做法是：初始时每个人都属于自己的集合，每来一条关系就把两个人所在的集合合并，最后数一下还有多少个集合。

这里面最关键的一点是：并查集不关心“A 和 B 是怎么连起来的”，也不关心中间经过了几个人，它只回答两个问题：

• find(x)：x 属于哪个集合？通常返回集合的“代表元素”（根）。
• union(x, y)：把 x 和 y 所在的两个集合合并成一个。

查询“x 和 y 是否认识”就变成find(x) == find(y)。就这么简单，所有并查集的花活都建立在find和union这两个动作上。

1.2 适合并查集的三个特征

我在实际做题和写代码时，总结出三个信号。只要问题同时满足这三条，大概率可以用并查集：

1. 只关心“是否连通”“是否同类”，不关心具体路径。一旦要输出路径，那就是图论里 BFS/DFS 或者最短路径算法的活了。
2. 操作里有大量“合并集合”。比如动态加边、把两个等价类并在一起。
3. 关系具有传递性。A 和 B 连通，B 和 C 连通，那 A 和 C 也一定连通；同类关系、朋友关系、网络可达性都满足这条。

反过来，什么时候别用并查集？我也列个清楚的对比表：

这套“特征判断法”比背模板有用得多。我见过不少同学拿着并查集往最短路径题上套，结果越套越乱，就是因为没想清楚第一点。

1.3 初始化的两种习惯

写并查集第一步是初始化。常见有两种写法：

// 写法一：parent[i] = i，根指向自己 for (int i = 0; i < n; ++i) parent[i] = i; // 写法二：parent[i] = -1，用负数表示根，同时用绝对值表示集合大小 vector<int> parent(n, -1);

第一种写法最直观，判断根就是parent[x] == x。第二种写法节省一个 size 数组，因为parent[root] = -size，但可读性差一点，我自己平时用第一种，笔试面试也推荐第一种，不容易写错。后面所有代码都基于parent[i] = i。

2. 朴素实现为什么慢，慢在哪儿

2.1 最直觉的“打标签”写法

很多人第一次接触“合并集合”，第一反应是维护一个标记数组label[i]，表示元素 i 属于几号集合。合并集合 A 和 B 时，把 B 里所有元素的 label 改成 A 的编号。

这个写法的问题一眼就能看出来：合并一次需要扫描整个数组，O(n) 复杂度。如果有 m 次合并，最坏就是 O(nm)。数据规模一大，比如 n=10万、m=10万，直接 100 亿次操作，跑题都要跑到超时。

2.2 用树表示集合：把慢的问题转移掉

聪明一点的做法是用树结构。每个集合看成“一棵树”，树根是这个集合的代表元素。parent[i]不再存集合编号，而是存 i 的父节点；根节点的 parent 指向自己。

• find(x)：从 x 沿着父指针往上爬，直到某个parent[root] == root，返回 root。
• union(x, y)：找到 x 和 y 的根，把一个根接到另一个根下面。

合并两棵树只需要改一个指针，O(1)；查找的耗时取决于树的高度。这个设计把“合并要扫描全集合”的高昂代价，转移成了“查找要走一条链”的代价。看起来很美，但有一个致命问题。

2.3 退化成链：一次糟糕的合并顺序毁掉一切

如果合并的时候不加任何策略，总是把后一棵树的根接到前一棵树的根下面，连续合并 1-2、2-3、3-4……树会越长越高：

1 ← 2 ← 3 ← 4 ← 5

此时find(5)要走 4 步，find(n)要走 n-1 步。合并 m 次、查询 m 次的复杂度就变成 O(n + m·n)，和打标签法半斤八两，甚至更糟。

这个退化问题是并查集所有优化的出发点。记住一句话：并查集的性能瓶颈从来不是合并且本身，而是查找时爬树的深度。

3. 两大优化：路径压缩与按秩合并

3.1 路径压缩：查一次就把路踩平

路径压缩的思想非常朴素：find(x)在从 x 爬到根的过程中，把沿途所有节点的父指针直接改成根。这样下次再查这些节点，一步就到根。

递归写法在代码上只有一行：

int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

这个写法把“找到根”和“路径上所有节点指向根”两件事一起干了。不熟悉递归的人可能看着晕，但它的语义很清晰：如果 x 不是根，先把 x 的父节点也 find 到根，然后把 x 的父指针指向根，返回根。

如果担心递归爆栈（后面我会专门讲这个坑），可以用迭代版完全压缩：

int find(int x) { int root = x; while (parent[root] != root) root = parent[root]; while (parent[x] != x) { int nxt = parent[x]; parent[x] = root; x = nxt; } return root; }

这两段代码维护的集合语义完全一样：路径压缩只是把树压矮了，并没有改变“哪些元素属于同一个集合”的事实。

3.2 按秩合并：永远让矮树接到高树上

路径压缩能把树压得很扁，但它解决不了“合并时把一颗很高的树接在另一颗更高树上”的情况。按秩合并就是给 union 加一条纪律：把高度小的树根，接到高度大的树根下面。

秩的定义有两种常见实现：一种是维护高度rank，一种是维护节点数sz。我平时更愿意按集合大小合并，因为 size 可以在后面统计集合大小时直接复用：

void unite(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; if (sz[ra] < sz[rb]) swap(ra, rb); parent[rb] = ra; sz[ra] += sz[rb]; }

为什么按大小合并能保证树高？因为一个节点所在树的大小，每经过一次合并至少翻倍。树高超过 log n 的前提是集合大小超过 2^log n = n，矛盾。所以单看按秩合并，能保证树高 O(log n)。

3.3 两个优化加起来：均摊复杂度逼近常数

教科书里最经典的结论是：只用路径压缩，m 次操作的摊还复杂度是 O((m+n) log n)；只用按秩合并，是 O(m log n)；两个同时用，复杂度是 O(m·α(n))，其中 α 是反阿克曼函数。

反阿克曼函数增长有多慢？慢到你几乎无法直观感受：即使 n 是宇宙中原子数量的级别，α(n) 也不会超过 5。所以在实际工程和竞赛里，你可以直接认为并查集“接近 O(1)”。

我用一个表格把复杂度演变放这儿，方便你复习时一眼看明白：

面试和考研如果问到“为什么并查集快”，你背下这张表的最后一列就够了。但要理解背后的原因：路径压缩让树越用越矮，按秩合并让树从一开始就不容易长高，两者是不同层面的保护。

3.4 只用一个优化够不够？

实际写代码时，只做路径压缩的并查集已经能跑得非常快，很多模板干脆只写 find 不写 rank。但我的建议是两个都写上。理由有三条：

• 只做路径压缩，构造数据可以把摊还复杂度卡到 O((m+n) log n)，虽然不算灾难，但没必要赌。
• 按秩合并保证了树的深度上界，这对“可撤销并查集”“可持久化并查集”这些进阶玩法是必要的——那些场景不能用路径压缩，只能靠按秩合并控制深度。
• 维护 size 数组额外成本极低，还能顺手支持查集合大小。

既然零成本，为什么不写？

4. 带权并查集：从“是否同类”到“偏了多少”

4.1 普通并查集只回答“是不是”，带权并查集回答“差多少”

普通并查集能回答“A 和 B 在不在同一个集合”，但很多问题要求更多：A 比 B 大 3，B 和 C 颜色相同，C 和 D 颜色相反……这时集合内部还要维护“相对关系”。

最经典的例子里，食物链算一个：A 吃 B，B 吃 C，C 吃 A。现在给你一串“x 吃 y”“x 和 y 同类”的陈述，让你判断哪些是假的。如果只用普通并查集，你只知道 x 和 y 是否在同一个关系图里，却不知道它们之间到底是谁吃谁。带权并查集就是干这个的。

4.2 核心思想：把相对关系看成模 k 的偏移

假设每个元素有一个“真实值” value(x)，我们不知道它具体是多少，但知道它和另一个元素的差值。定义off[x]表示 x 相对根的值差：

off[x] = value(x) - value(root(x)) (mod k)

其中 k 是关系总数。比如只有“同类/异类”两种关系，k=2；食物链三类关系，k=3。

find(x)不再只是把父指针指向根，还要同步更新 off。递归时顺序很关键：

int find(int x) { if (parent[x] != x) { int p = parent[x]; parent[x] = find(p); off[x] = (off[x] + off[p]) % k; } return parent[x]; }

注意必须先让 p 的父指针也指向根、p 的 off 更新为“p 到根的偏移”，然后才能把 x 的旧偏移（x 到 p）加上 p 的新偏移（p 到根）。顺序一乱，off 就全乱了。

合并操作要解决的是：已知value(x) ≡ value(y) + c (mod k)，如果 x 和 y 不在同一个集合，怎么把两个集合并起来？假设把 ry 挂到 rx 下面，需要算off[ry] = value(ry) - value(rx)。推导过程：

value(x) = off[x] + value(rx) value(y) = off[y] + value(ry) 已知 value(x) ≡ value(y) + c => off[x] + value(rx) ≡ off[y] + value(ry) + c => value(ry) - value(rx) ≡ off[x] - off[y] - c (mod k)

所以：

// 设定 value(x) ≡ value(y) + c (mod k) bool unite(int x, int y, int c) { c = (c % k + k) % k; int rx = find(x), ry = find(y); if (rx == ry) { // 同集合，验证已有关系是否满足条件 return (off[x] - off[y] - c) % k == 0; } parent[ry] = rx; off[ry] = (off[x] - off[y] - c + k) % k; return true; }

这里最容易被绕晕的地方是“方向”。不同教程里 off 的定义方向可能相反，有的用“根到 x 的偏移”，有的用“x 到根的偏移”，公式符号就会差一个负号。我的建议是：自己固定一种定义（比如上面这种），把推导过程在纸上走一遍，之后就永远用这一套，不要背别人的公式。

4.3 食物链：模 3 的经典应用

食物链题（POJ 1182）里的关系是循环的：0 吃 1，1 吃 2，2 吃 0。如果给三类动物编号 0、1、2，那么“x 吃 y”可以表达为value(x) ≡ value(y) + 1 (mod 3)，“x 和 y 同类”就是value(x) ≡ value(y) + 0 (mod 3)。

读入每句话时：

• 若是“x 和 y 同类”，调用unite(x, y, 0)。
• 若是“x 吃 y”，调用unite(x, y, 1)。
• unite返回 false 就说明这句话和之前已知的事实矛盾，是假话。

难度不在并查集本身，而在于把“吃”的关系翻译成差值。翻译对了，代码就是模板的机械重复。

4.4 另一个方向：扩展域并查集

带权并查集不是处理“相对关系”的唯一办法。当关系类型很少（最常见的就是“相等/不等”两种），可以用扩展域：把每个变量拆成多个点。

比如 LeetCode 990 的等式方程题，变量只有 0/1 两种取值，每个变量 x 拆成两个结点：x 表示“x 为 0”的命题，x+n 表示“x 为 1”的命题。

• 已知 x == y：合并 (x, y) 和 (x+n, y+n)。
• 已知 x != y：合并 (x, y+n) 和 (x+n, y)。

如果最后发现 x 和 x+n 被并到了同一个集合，说明“x 同时等于 0 又等于 1”，矛盾。

那什么时候用带权，什么时候用扩展域？我的经验是：关系是模 k 循环/差值的，用带权；关系只有“同/不同”两类、并且可以拆成若干个明确命题的，用扩展域。扩展域代码稍微长点，但逻辑更好理解，不容易把符号搞反。

5. 一份能直接抄的模板，以及两个经典题目复盘

5.1 我自己常用的 C++ 模板

以下是我平时做题用的普通并查集模板，带路径压缩和按 size 合并：

class DSU { public: vector<int> parent, sz; DSU(int n) : parent(n + 1), sz(n + 1, 1) { for (int i = 0; i <= n; ++i) parent[i] = i; } int find(int x) { int root = x; while (parent[root] != root) root = parent[root]; while (parent[x] != x) { int nxt = parent[x]; parent[x] = root; x = nxt; } return root; } bool unite(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return false; if (sz[ra] < sz[rb]) swap(ra, rb); parent[rb] = ra; sz[ra] += sz[rb]; return true; } };

默认下标从 0 到 n-1。如果你需要从 1 开始编号，构造时多传一个 n+1 就行，其他不用改。

带权版本就用前面写的WeightedDSU，unite(x, y, c)的语义是“设定 value(x) ≡ value(y) + c (mod k)”。这套定义我用了很久，推导过两次之后基本不会错。

5.2 Python 的写法：注意递归深度

Python 写并查集有个隐藏坑：默认递归深度大概只有 1000。如果数据规模大，递归版 find 分分钟 RecursionError。所以 Python 版我一般写迭代完全压缩：

class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n def find(self, x): root = x while self.parent[root] != root: root = self.parent[root] # 第二遍循环做完全路径压缩 while self.parent[x] != x: nxt = self.parent[x] self.parent[x] = root x = nxt return root def unite(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] return True

Python 里也可以用sys.setrecursionlimit(10**6)强行放开递归限制，但迭代版更稳。带权并查集在 Python 里如果必须递归，我通常只在小数据上这么写，或者用栈模拟递归来更新 off。

5.3 题目复盘：省份数量（LeetCode 547）

这题给的矩阵isConnected[i][j] = 1表示 i 和 j 直接相连，让你数有多少个省份（连通分量）。用并查集就是无脑合并：

DSU dsu(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (isConnected[i][j]) dsu.unite(i, j); int ans = 0; for (int i = 0; i < n; ++i) if (dsu.find(i) == i) ++ans;

核心技巧在最后统计：根节点满足find(i) == i，数一下有几个根就是几个连通块。这个技巧比用 set 去重所有 find 结果更快。

5.4 题目复盘：等式方程的可满足性（LeetCode 990）

这题给一堆a == b和a != b的等式，问有没有可能全部满足。关键点是：先把所有等号处理完，再处理不等号。

DSU dsu(26); // 26 个字母 for (auto &e : equations) if (e[1] == '=') dsu.unite(e[0] - 'a', e[3] - 'a'); for (auto &e : equations) if (e[1] == '!' && dsu.find(e[0] - 'a') == dsu.find(e[3] - 'a')) return false; return true;

为什么要分两遍？因为a == b和b == c合并之后，你才能知道a和c也必须相等；如果a != c在合并前检查，它们当时可能还不在一个集合，就会漏掉矛盾。做题时最容易踩的坑就是边读边判断，这类题以后都记住：先合并所有相等约束，再验证所有不等约束。

6. 工程实战中的并查集，以及我踩过的坑

6.1 除了刷题，工程里真有用到吗

很多人觉得并查集就是面试/考研题，工程用不上。实际上我用过的地方包括：

• Kruskal 最小生成树：边按权值排序，依次尝试加入。每次要快速判断“加这条边会不会成环”，并查集一句find(u) == find(v)就搞定。这是算法课之外最典型的并查集应用。
• 图像连通区域标记：把像素坐标压成一维索引，像素值相同的相邻像素做 union，最后统计根的数量就是连通区域个数。
• 编译器/数据库里的等价类合并：当两个变量被约束为相等时，本质上就是把两个等价类合并，之后传递等式的判断都是并查集操作。
• 社交网络反作弊/社群检测的预处理：把“同一个设备登录过的账号”合并成集合，后续分析直接以集合为单位。

套路都一样：把元素映射成下标，把“等价/连通”翻译成 union，把“是否相同”翻译成 find。大家如果只盯着代码，很容易忽略这个抽象层，但工程上真正值钱的其实是这层翻译能力。

6.2 坑一：递归 find 在大数据下会爆栈

有一次我在本地跑 10 万节点的并查集，递归版 find 直接段错误。原因很简单：虽然路径压缩让树很矮，但如果你还没做几次查找，树还很高，递归调用的层级就可能达到几千甚至上万层。

解决方式有两个：一是改用迭代版完全压缩（前面代码已经给了）；二是如果必须用递归版，至少在主函数里把栈空间调大。我个人的原则是：普通并查集一律写迭代版，只有带权并查集才用递归版——因为带权 find 需要回溯父节点来更新偏移，迭代版写起来繁琐且容易错。

6.3 坑二：下标从 0 还是 1，二维坐标怎么压

坐标压成一维是并查集工程化的常见需求。比如一个 m 行 n 列的网格，点 (i, j) 映射成i * n + j，然后parent数组开m * n。下标统一从 0 开始，不然你会在parent[x * n + y + 1]这种地方反复越界。

如果你的节点不是连续整数，比如是字符串 IP、账号 ID，可以用一个unordered_map<string, int>做懒散列映射：第一次见到某个 key 时把它分配一个新下标。这相当于动态扩容的并查集，写起来也很顺手。

6.4 坑三：并查集没有“撤销”操作

标准并查集只支持合并，不支持把两个集合重新拆开。遇到“动态删边”类问题怎么办？一个常用套路是离线倒序处理：既然删边难，那就先把所有操作读完，确定最终状态，然后从后往前“加边”，把删边问题转化成加边问题。工程里大多数需要“删边”的场景都可以这样迂回解决。

更进阶的可撤销并查集，做法是：不用路径压缩，只用按秩合并，并把每次 union 修改的父节点和 size 记录在栈上，回滚时弹栈恢复。这就是为什么我前面强调“按秩合并”不只是性能优化，还是可撤销玩法的基础。

6.5 坑四：带权并查集的取模和方向，错一个全盘崩

带权并查集最磨人的不是公式推导，而是方向。我见过太多人背了食物链模板却不知道每行的意思，换道题就死。调试经验有两个：

• 画一棵三节点的小树，手动走两遍 find，把 off 的更新过程写出来，看和代码逻辑是否一致。
• 写一个暴力验证程序，小规模随机数据，用普通数组模拟集合逐个验证，和并查集结果对拍。我个人几乎所有带权并查集的题都是靠对拍过的，因为手推太容易漏掉模的边界。

取模千万别忘了先把负数修正成非负数：((x % k) + k) % k。C++ 的%对负数会返回负值，这一步漏了，后面全出问题。

最后说说我自己的体会。并查集代码短，看起来十几行，但它是我见过的“原理和实战差距最大”的数据结构之一。你把find的路径压缩、union的按秩合并、带权版本的偏移更新这几件事真正在纸上推过一遍之后，后面再学可撤销并查集、可持久化并查集、树上带权并查集会顺很多。建议大家拿到任何并查集题目，先把“关系如何翻译成差值”写下来，再动代码，不要上来就套模板——我踩过的所有坑，几乎都是因为跳过了这一步直接开写。