企业官网建设流程全解析

不少人刚开始学并查集时，都觉得这玩意儿也太简单了——维护一堆元素属于哪个集合，查一查根，合并一下，完事。可一旦题目换个马甲，比如告诉你“A吃B、B吃C、C吃A”，或者给你一串“区间内1的个数是奇数还是偶数”的条件让你找矛盾，普通并查集就明显不够用了。这时候就要上一层楼，接触到种类并查集和带权并查集。这篇文章我打算把这三层一次讲透，从底层原理到代码实现，再到调试技巧，实操性拉满。无论你是准备考研数据结构、应付期末考试，还是刷 LeetCode、搞算法竞赛，认真看完应该都能有收获。

1. 并查集解决的到底是个什么问题

1.1 动态连通性：一个比想象中更常见的需求

并查集的原始模型非常朴素：有 n 个元素，初始时每个元素单独形成一个集合。支持两种操作：把两个元素所在的集合合并成一个，以及查询两个元素是否在同一个集合里。这类问题在算法里有个专门的名字，叫动态连通性。

我举个生活中的例子。假设你在运营一个兴趣社团系统，用户 A 加入了羽毛球群，羽毛球群和跑步群合并了，跑步群里又有 B。你随时要回答“A 和 B 当前是不是在同一个群体系里”。如果用户量只有几十个，你用数组给每个人打集合编号，每次合并重新遍历一遍也能忍。可一旦数据量到了十万、百万级，合并一次就遍历所有人，操作次数一多直接崩盘。

这还没完。并查集在算法题里几乎是无处不在的配角。最小生成树 Kruskal 算法要判断“加上这条边会不会成环”，本质就是查询两个点的连通性；离线处理区间合并问题要先按某种顺序把相邻位置合并起来；图论里统计连通分量个数也常直接套并查集。包括工程里做依赖分组、网络设备连通性检测，很多场景其实都能抽象成“合并集合 + 查询关系”。

所以，如果你只把并查集当成“教材里的一个数据结构”去背，它的价值你就只吃到了十分之一。真正该理解的是，它为什么能在近似 O(1) 的时间里完成这些操作，以及它后续演化出的“种类”和“带权”版本，能表达多么丰富的关系模型。

1.2 为什么用树来组织，而不是给每个人重写编号

先说说最常见的错误直觉：给每个集合记录一个编号，再维护一个数组belong[x] = 集合编号。查询两个元素是否同集合只需要比较编号，O(1)，快得很。问题出在合并：要把一个集合的所有元素的belong改掉，就必须遍历这个集合里每一个元素。哪怕你聪明地选择把小的集合合并进大的集合，最坏情况下整体复杂度依然可以达到 O(n log n) 级别，而且编码复杂度很高，多个集合反复合并时会非常痛苦。

并查集换了个思路：每个集合不存“编号”，而是一棵有向的树，根节点就是集合的代表元素。每个节点都存一个父指针fa[x]，指向它的上一级。合并两个集合时，我只需要找到两个集合的根节点，然后把其中一个根节点的父指针指向另一个根节点——这就是一次 O(1) 的指针操作。查询时，沿着父指针一层层向上走，直到根节点，就能确定代表元素。

这个思想用一句话总结就是：合并动作本身不折腾下层节点，只折腾代表节点。就像两个班级合并，不需要让全班所有人都互相握手，两个班长碰个头，全校的“归属关系”就确定了。后续任何人想知道自己属于哪个班，沿着“学生→班长→年级负责人”这条链一路向上找就行。

当然，如果树的形态退化成一条链，每次查询都要 O(n) 地往上走，用并查集反而比暴力还慢。所以就有了路径压缩和按秩合并这两个优化，这也正是并查集真正封神的原因。

2. 手写一个趁手的并查集：代码与优化细节

2.1 最简版本：先能用，再谈优化

先直接给出一份最朴素的并查集实现，你们感受一下代码量：

const int N = 100010; int fa[N]; void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; } int find(int x) { if (fa[x] == x) return x; return find(fa[x]); } void merge(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) fa[fx] = fy; } bool query(int x, int y) { return find(x) == find(y); }

核心就两个函数。find递归向上找根，merge把一棵树的根挂到另一棵树的根上。query就是find的比较。这里的fa[i] = i初始化很重要，它表示每个节点在一开始都是自己的根，也就是“自成一派”。

这个版本在数据量小、或者操作次数少时完全够用。但注意，如果不断把链式结构合并，比如依次 merge(1,2)、merge(2,3)、merge(3,4)……这棵树会越来越像一根甘蔗，find(4)要往前跳 4 次，find(100000)要跳十万次，复杂度直接爆炸。

我当年第一次在竞赛里用未优化的并查集，就被一组精心构造的数据卡到怀疑人生。从那以后我写并查集，基本默认带上下面这两个优化。

2.2 路径压缩和按秩合并，哪个更重要

所谓路径压缩，就是在find返回根节点的过程中，顺手把路径上所有经过的节点直接指向根。这样以后查询这些节点时，一步就能到根，无需再层层往上爬。

int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); }

注意这行fa[x] = find(fa[x])，它不仅仅是递归调用，还做了一个赋值操作——把 x 的父指针直接指向递归返回的根节点。这就是路径压缩的关键。

所谓按秩合并，指的是合并时尽量把“矮树”接到“高树”下面，避免树长高。实操中通常用集合大小来替代树高，也就是常说的按大小合并：

int fa[N], sz[N]; void init(int n) { for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } } int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } void merge(int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return; if (sz[fx] > sz[fy]) swap(fx, fy); fa[fx] = fy; sz[fy] += sz[fx]; }

这里sz[x]表示以 x 为根的集合里有多少个元素。合并时，如果发现sz[fx] > sz[fy]，就先交换，保证总是把小的集合挂到大的集合上。这样树的深度增长是 O(log n) 级别的。

那是不是两个优化必须同时上？理论分析告诉我们：单独使用路径压缩时，总复杂度是 O(m log n)；单独使用按秩合并时，总复杂度也是 O(m log n)。只有两者同时使用，均摊单次操作复杂度才达到反阿克曼函数 O(α(n))，这是一个增长极其缓慢的函数，可以认为小于 5。

实际做题时，我基本总会一起用。因为它们各自只多几行代码，带来的收益却是指数级的。但面试或者考试里如果只让你描述“并查集的基本操作”，别忘了把“路径压缩”和“按秩合并”挂到嘴边，这是两个标志性的优化点。

这里还有一个容易被忽略的细节：递归的find在极端情况下会爆栈。虽然路径压缩会让树高很矮，但如果在递归过程中调用非常深，仍有风险。比赛里可以用非递归写法，比如循环先找到根，再沿着路径做第二次循环赋值。不过我自己的习惯是先用递归版，只有当题目数据规模达到百万级以上，才会换成非递归版本。

3. 种类并查集：当集合里不止一种关系

3.1 朋友的敌人是不是你的敌人？普通并查集答不了

普通并查集只能表达“在同一个集合”或“不在同一个集合”这种二元关系。但现实世界里的关系远没这么简单。经典例子就是“敌人的敌人是朋友”。假设 A 和 B 是敌人，B 和 C 是敌人，那你不能简单地把 A 合并到 B，再把 C 合并到 B，因为 A 和 C 在逻辑上应该是一伙的，可普通并查集里它们各自和 B 的关系是没法区分的。

竞赛里还有个流传极广的题目原型——“食物链”：三种动物循环捕食，A 吃 B，B 吃 C，C 吃 A。现在给你一串描述，有的说“X 和 Y 是同类”，有的说“X 吃 Y”，让你判断哪些话和前面已知条件是矛盾的。

这种题目如果你只维护一份并查集，完全无从下手，因为你需要的不是“是否同类”这一个信息，而是“同类、猎物、天敌”三种角色关系。这时候有两个主流解法，一个叫扩展域并查集，一个叫带权并查集。我先讲更直观的扩展域。

3.2 扩展域写法：把一个点拆成多个角色

扩展域的思想很朴素：既然每个元素有多个角色，那我就把每个角色都当成一个独立的点放进并查集里。以上面的“食物链”为例，对第 i 个动物，我开出三个点：

• i表示“i 自己”这个角色；
• i + n表示“i 的猎物”这个角色；
• i + 2n表示“i 的天敌”这个角色。

这样总节点数是 3n。初始时，所有角色都各自成集合。接下来每来一条信息，我不是只合并“两个元素”，而是合并“相关的角色集合”。

比如“X 和 Y 是同类”，那意味着：X 自己的集合和 Y 自己合并；X 的猎物集合和 Y 的猎物合并；X 的天敌集合和 Y 的天敌合并。也就是把三个角色完全对齐。

“X 吃 Y”怎么合并？这句话等价于：X 的猎物是 Y，X 是 Y 的天敌，同时 X 的天敌是 Y 的猎物（因为食物链是一个环，A吃B、B吃C、C吃A，所以天敌的猎物之间也有关联）。所以要做三次合并：

void unite(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) fa[fx] = fy; } void same(int x, int y) { // 声明x和y是同类 unite(x, y); unite(x + n, y + n); unite(x + 2 * n, y + 2 * n); } void eat(int x, int y) { // 声明x吃y unite(x + n, y); // x的猎物是y unite(x, y + 2 * n); // x是y的天敌 unite(x + 2 * n, y + n); // x的天敌是y的猎物 }

判断矛盾时也很直观。如果某句话声称“X 和 Y 是同类”，但现有的并查集里已经有了find(X + n) == find(Y)（说明 X 的猎物是 Y，也就是 X 吃 Y），或者find(X + 2 * n) == find(Y)（说明 X 的天敌是 Y，也就是 Y 吃 X），那这句话就是假的。

如果某句话声称“X 吃 Y”，但现有的并查集里已经能推出find(X) == find(Y)（同类）或者find(X + 2 * n) == find(Y)（说明 X 的天敌是 Y，也就是 Y 吃 X），那它也是假的。

这个思路的优势是逻辑清晰，不太需要推导复杂的数学公式，懂并查集基本操作的人很快能上手。缺点是空间变大了，如果有 k 种角色，就要开 k*n 的数组。但一般 k 都很小，比如 2、3，所以完全能接受。

3.3 开两倍数组的典型场景：朋友与敌人

不只是三倍数组，很多“二分关系”题目只需要开两倍数组。比如最常见的“朋友与敌人”问题：A 和 B 是敌人，B 和 C 是敌人，问 A 和 C 是不是朋友。

这种题的处理方式是：i表示 i 所在的“朋友阵营”，i + n表示 i 所在的“敌人阵营”。当 X 和 Y 是朋友时，合并X与Y，合并X+n与Y+n；当 X 和 Y 是敌人时，合并X与Y+n，合并X+n与Y。

很多初学者会好奇：为什么敌人关系要交叉合并？因为如果 X 和 Y 是敌人，那么 X 的朋友就是 Y 的敌人，X 的敌人就是 Y 的朋友。这个交叉合并把“敌人的敌人是朋友”这条隐式规则编码进了并查集。一旦后续发现find(X) == find(Y)，说明朋友阵营重合，那就矛盾了。

所以，种类并查集的本质，是用“多开几个集合”的方式，把原本只能表达“正反”两类关系的问题，扩展为能够表达“正、反、中立”、“猎物、天敌、同类”等多角色关系。当你遇到“对于任意两个元素，它们之间可能有多种互斥关系”的题目时，第一时间就该想到扩展域。

4. 带权并查集：从“连通”升级到“距离”

4.1 边上的权值到底在表达什么

如果扩展域的核心是“多开几个集合”，那带权并查集的核心就是“给每条边加一个数值”。这个数值可以表示相对关系、相对距离、奇偶差异等，完全取决于题目语义。

举个最简单的例子：现在有一排位置，每个位置放一个数字。告诉你一系列条件，比如“区间 [l, r] 内所有数字的和是奇数”，或者“A 比 B 的权重大 3 个单位”。你不仅要判断这些条件是否矛盾，还要在某些情况下计算两个点之间的差值。这时候普通并查集的fa[x]只有一个父节点信息，远远不够用。

带权并查集的做法是在fa[x]之上，再维护一个d[x]，表示节点 x 到父节点fa[x]的“距离”或“关系值”，在模 M 的意义下取值。这里的 M 取决于关系种类数或者问题的模数。比如食物链问题中，0 表示同类，1 表示吃，2 表示被吃，M=3；奇偶性问题中，0 表示偶数，1 表示奇数，M=2。

当你查询根节点并做路径压缩时，d[x]要一路累加上去，最终变成 x 到根节点的权值。这个过程需要格外小心，因为递归本身容易把顺序搞乱。

4.2 路径压缩时的权值更新写法

先看最常用的递归写法：

int fa[N], d[N]; // d[x] 表示 x 到 fa[x] 的权值，模 mod int find(int x) { if (fa[x] == x) return x; int root = find(fa[x]); // 先递归找到根 d[x] = (d[x] + d[fa[x]]) % mod; // 此时 fa[x] 已经被递归地压缩为根了 fa[x] = root; return fa[x]; }

为什么这里d[x] + d[fa[x]]是对的？因为递归调用find(fa[x])之后，fa[x]这个位置已经被更新成了整个集合的根，同时d[fa[x]]也更新成了原 fa[x] 到新根的权值。所以 x 到根的权值 = 原来的 d[x]（x 到旧父亲）+ 旧父亲到根的权值 d[fa[x]]。最后赋值fa[x] = root完成路径压缩。

更保险的写法是先保存旧父节点：

int find(int x) { if (fa[x] == x) return x; int old = fa[x]; int root = find(old); d[x] = (d[x] + d[old]) % mod; fa[x] = root; return root; }

两种写法本质一样，第二种对新手更友好，不容易在递归过程中被“奇怪的顺序”绕晕。

4.3 合并时的权值推导：别硬背公式，要会推

合并操作是带权并查集最容易出错的地方。假设现在有一条信息：“x 和 y 的关系值为 r”（仍然在模 M 意义下，具体 r 的含义由题目定义）。x 所在集合的根是fx，y 所在集合的根是fy。我要把fx挂到fy下面，那么新的d[fx]应该等于多少？

这里不能靠默写，得自己推一遍。先明确符号：

• d[x]表示 x 到fx的权值；
• d[y]表示 y 到fy的权值；
• 题目给出的条件是 x 到 y 的关系值为 r。

合并后fa[fx] = fy，我们需要的是d[fx]，也就是 fx 到 fy 的权值。

从 fx 出发，沿着d[fx] + d[x]这条路径能走到 x；从 x 再到 y 需要关系 r；从 y 再到 fy 需要d[y]。合并后，整条路径应该自洽，也就是说：

d[fx] + d[x] + r = d[y]（在模 M 意义下）

移项得到：

d[fx] = d[y] - d[x] - r

但不同题目的 r 方向定义不同，有的定义是“x 到 y 的关系”，有的是“y 到 x 的关系”，所以代码里可能出现d[fx] = (d[y] - d[x] + r) % mod这样的式子，也可能出现减号。关键是别背公式，每次做新题时先画一条路径，自己推一遍方向。

实现时为了防止负数，通常会这样写：

void merge(int x, int y, int r) { int fx = find(x), fy = find(y); if (fx == fy) return; fa[fx] = fy; d[fx] = ((d[y] - d[x] + r) % mod + mod) % mod; }

注意这行后面先取模再加mod再取模，确保结果落在[0, mod-1]区间。

4.4 实战理解：奇偶性问题如何用带权并查集

这类题的经典问法：给你一个 01 序列，然后给出一串条件，每个条件说“区间 [l, r] 内 1 的个数是奇数还是偶数”，让你判断最早在第几条条件处出现矛盾。

思路是维护前缀和数组pre[i]，区间 [l, r] 内的奇偶性等于pre[r] xor pre[l-1]。我们不需要知道前缀和的具体数值，只需要知道任意两个前缀和的奇偶关系是否自洽。于是把pre[l-1]和pre[r]当成两个节点，用带权并查集维护它们的异或值（也就是模 2 意义下的差值）。

• 如果条件说区间内是“偶数个 1”，则pre[l-1]和pre[r]奇偶性相同，关系值 r = 0；
• 如果条件说区间内是“奇数个 1”，则pre[l-1]和pre[r]奇偶性不同，关系值 r = 1。

每次拿到新条件，先查询fx = find(l-1)和fy = find(r)。如果已经在同一个集合里，就检查当前已知的d[l-1]和d[r]计算出的奇偶关系是否和题目给的一致，不一致就是矛盾。如果不在同一个集合，就执行带权合并。

这种问题如果不提前想到“前缀和奇偶性”这个转化，哪怕你背熟了带权并查集代码也想不到要这么用。所以带权并查集真正难的往往不是代码，而是把题目条件抽象成“两个点的权值差”这个建模过程。多看几道典型题，慢慢就会建立条件反射。

5. 常见问题、调试技巧与适用场景速查

5.1 那些年我踩过的并查集坑

先列几个新手极容易踩的坑，每一条我都亲眼见过或者自己踩过。

第一，初始化漏了。fa[i] = i没写全，或者下标从 0 开始但循环只到了 n-1，查询时直接访问到没初始化的垃圾值。这是最基础但也最高发的错误，没有之一。

第二，递归 find 爆栈。路径压缩并不是银弹，如果并查集合并时没按秩合并，又连续做了很多次合并，递归深度仍然可能很大。比赛里我见过有人因为递归爆栈导致 RE，而不是 WA。大数据量时，建议还是写循环版。

第三，合并时根选反了。比如merge(x, y)里写成fa[y] = x，虽然对于普通并查集查询连通性影响不大，但在带权并查集里，方向一旦反了，所有d的推导全部颠倒，最后出一堆莫名其妙的结果。

第四，模运算负数处理。带权并查集的d[fx]计算时，d[y] - d[x] + r可能是负数。如果直接对负数取模，不同语言对负数的处理不一样，很容易出问题。统一写成((val) % mod + mod) % mod。

第五，路径压缩时d[x]更新顺序错。新手容易写成d[x] += d[fa[x]]，但此时fa[x]已经是经过递归压缩后的根，如果没先用一个临时变量保存旧父节点，最后算出来的权值会差很远。

5.2 一个很容易复制的调试套路

调试并查集问题最直接的方法：写一个小的暴力版本，然后随机数据对拍。

具体做法是，维护一份朴素的、不含路径压缩的并查集，或者直接在每次操作后用 DFS 遍历整个集合看连通关系，再和优化版的答案对比。对拍数据要覆盖随机合并、随机查询、随机矛盾条件。一旦发现两边答案不一致，立刻把出错的那组输入打出来，手动模拟。

如果只是单纯调试带权并查集，很多人会盯着代码看半天也看不出所以然。我更喜欢在每个关键操作后打印fa数组和d数组，比对样例的每一步。写一个简单的debug()函数，输出所有节点的父节点和权值，观察在哪一步开始和预期不符，问题通常就一目了然。

另一种有效手段是拿一道题的两个版本互相验证：扩展域版本和带权版本各写一遍，对拍验证，这样不仅验证了代码正确性，还能加深理解。我就曾经用食物链这题，把扩展域和带权写法都写了一遍，从此对带权并查集的公式推导有了一种“肌肉记忆”。

5.3 哪些场景用普通、种类还是带权

整理一个速查表，方便做题时快速定位该用哪一型。

这张表只是一个大方向，实际题目经常要混合使用。比如某些题用种类并查集描述角色，但每个角色内部还带权值，那就要组合。

5.4 复杂度与学习路径建议

普通并查集在同时使用路径压缩和按秩合并后，单次操作均摊时间复杂度为 O(α(n))，这里 α(n) 是反阿克曼函数，增长速度比 log n 还要慢得多，在实际数据范围内完全可以当成常数看待。种类并查集因为多开了 k 倍数组，空间是 O(kn)，时间仍然是 O(α(kn))。带权并查集只在每次 find 时多做几次加法和取模，时间依然稳定在接近常数的水平。

学习路径上，我不建议一上来就盯着黑皮书里的各种证明看。正确的顺序应该是：先把普通并查集背熟，然后用“食物链”这题分别用扩展域和带权写法各做一遍；再做两道“奇偶游戏”和“带权排名”的题；最后回头看原理。你会发现，底色其实都是同一个东西：在“合并集合”之上表达“关系”，关系的表达要么靠多开集合，要么靠边权。

6. 写在最后：一点个人的体会

写并查集这几年，我最大的感受是：它是一个“易学难精”的典型。入门只需要 10 分钟，但真正在题目里用对、用活，需要积累很多模型。比如看到区间条件就想到前缀和节点，看到多种角色关系就想到扩展域或带权，这种条件反射不是靠背模板能建立的，必须靠实战喂出来。

我自己刷题时有个习惯，每遇到一种新的“关系判定类”模型，就会研究它能不能用并查集建模。就算某道题正解是线段树或者平衡树，我也会先想想并查集版本的思路，哪怕最后不用，这个思考过程也让我对并查集的边界有了更清晰的认知。话说回来，面试和考试里并查集的出现频率非常高，性价比确实拉满。如果你正被这东西绕得头大，不妨先把最基础的手写版跑通，再用食物链练手，我觉得收获会来得很快。