企业官网建设流程全解析

刷题刷到 D006【模板】并查集 这道题的时候，我第一次认真琢磨"模板题"三个字的含义。以前总觉得模板题就是让你把代码背下来，考试时候默写出来就完事。但并查集这个模板，真不是背一背就能应付的——它背后的"集合怎么存、怎么找代表元、怎么合并"这三个问题，才是整个数据结构的灵魂。这篇就借 D006 这道模板题，把并查集的原理、两种优化、常用变体、还有我自己踩过的坑，从头到尾捋一遍。适合刚学算法竞赛的选手，也适合刷了很多题但一直没真正搞懂并查集细节的人。

1. 模板题背后的三个核心问题：集合怎么存、怎么找、怎么合并

1.1 为什么一张普通数组就能表示一堆集合

并查集处理的问题永远是同一个形状：现在有 n 个元素，一开始每个元素各成一派；接下来会有若干次操作，要么把两个元素所在的集合合并，要么问两个元素在不在同一个集合里。如果你第一次接触这个结构，很容易想到用链表、用 vector 套 set，但那些都不合适。链表的合并确实快，但查询"两个元素是否在同一集合"要遍历，太慢。

并查集的精妙之处在于，它只用一张fa数组就完成了全部工作。fa[i]存的是 i 的父亲节点编号。如果fa[i] == i，说明 i 是这棵树的根，也就是这个集合的代表元。逻辑上，每个集合都长成一棵树，树根是"老大"，其余节点通过fa指针一层层指向根。这样设计最大的好处是：判断两个元素是否同属一个集合，不需要知道树长什么样，只需要看它们的根是不是同一个。

我最初学的时候觉得这个设计很反直觉，因为树的父子关系是有方向的，但并查集只关心"谁是谁的根"，完全不关心节点的儿子有哪些。这种"只保留必要信息"的思路，恰恰是并查集能保持简单的根本原因。

1.2 find 操作的路径追踪逻辑

find 要回答的问题只有一个：x 所在集合的代表元是谁。实现上就是沿着fa指针往上找，直到找到一个满足fa[i] == i的节点。

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

这个最朴素的写法在数据量小的时候没问题，但一旦树退化成一条链，find 的复杂度就是 O(n)，整道题直接起飞。所以后面几乎所有模板都会在 find 里加上路径压缩，把向上找根的过程中经过的所有节点，直接接到根下面，让树变得扁平。

这里有一个特别容易忽略的细节：路径压缩是在 find 的过程中完成的，也就是说，每次调用 find，都会顺手把沿途节点"拉平"一部分。所以并查集的复杂度分析必须考虑这种"查询顺便修改结构"的行为，这也是它最终能达到近似常数复杂度的原因。

1.3 union 合并操作的"谁并谁"问题

合并两个集合，在树视角下就是把一棵树的根接到另一棵树的根上。但"谁接谁"不是随便拍的，这直接决定了树的形状。

void unite(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return; fa[rx] = ry; }

如果永远让左边的根接右边的根，极端情况下会形成一条特别长的链，后续 find 效率爆炸。所以正经模板里一定会加一个秩的判定：要么让高度小的树接到高度大的树下（按秩合并），要么让规模小的树接到规模大的树下（按大小合并）。我在 D006 上用的大小合并，后面会细说。

这个"先 find 再判断，最后才动 fa"的顺序也值得留意。很多新手第一次写 union 时，喜欢直接写fa[find(x)] = find(y)，虽然结果对，但中间反复 find 会让代码的可读性和后续扩展都变差。我自己的习惯是先把根取出来存成变量，后面所有操作都用这两个根变量，避免在长表达式里埋 bug。

2. 两种优化各有分工：路径压缩负责"平"，按秩合并负责"矮"

2.1 路径压缩的实现与边界

路径压缩的标准递归写法是：

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

fa[x] = find(fa[x])这句话做了两件事：先递归找到根，然后把 x 直接指向根。递归返回时，沿途的所有节点都会依次被设置成根的直系孩子，树的高度瞬间被压缩。

如果担心递归爆栈（比如 n 到 1e6 级别，或者某些 OJ 栈空间很小），可以用迭代写法：

int find(int x) { int root = x; while (fa[root] != root) root = fa[root]; while (fa[x] != root) { int next = fa[x]; fa[x] = root; x = next; } return root; }

这段代码我第一次看的时候觉得有点绕，它的思路是：第一遍循环先找到根，第二遍循环把路径上所有节点逐个指向根。这两遍循环缺一不可，少了第二遍就不是路径压缩了。

2.2 按大小合并到底在保护什么

路径压缩能让一棵很高的树变矮，但它只有在 find 被调用时才会触发。如果你只做合并操作，从不查询，那树还是可能长成链。所以还要靠合并时的策略从源头控制树高，这就是按秩合并的价值。

我平时用的模板一般带一个sz数组，sz[i]只对根节点有意义，表示这棵集合树有多少个节点。合并时，让节点数少的树接在节点数多的树下面：

void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); fa[y] = x; sz[x] += sz[y]; }

这样做的收益是：不管怎么合并，树高最多是 O(log n)。因为一个小集合每次接在大集合下面，它的深度最多加 1，而它所在集合的大小至少翻倍，所以每个节点的深度不会超过 log n。这个"集合大小翻倍"的分析思路，在很多数据结构的复杂度证明里都会出现，理解了这一层，以后学左偏树、启发式合并都会轻松很多。

2.3 为什么复杂度接近 O(1)：反阿克曼函数的直觉

网上都说同时用路径压缩和按秩合并，单次操作复杂度是 O(α(n))，α 是反阿克曼函数。这个函数增长慢到什么程度？对于宇宙中所有原子数量级别的 n，α(n) 都不超过 5。所以你完全可以把它当作常数看。

但这里我要说一个反直觉的点：即使只用路径压缩、不用按秩合并，并查集的均摊复杂度也接近 O(log n)，实际跑起来通常也很快。我在 D006 上最初只写路径压缩，AC 没有问题。后面加上按大小合并，代码多几行，但心里更稳，尤其是在链式数据比较阴险的题目里，能明显感觉到速度差异。这是我的一个习惯：模板题里就把两种优化都写上，考场上永远不用赌数据。

下面把两种优化组合后的复杂度情况整理成一个表，方便对照：

3. 一份可复用的并查集模板，以及 D006 上的逐行解读

3.1 模板代码与每个成员的用途

下面这个结构体是我在 D006 之后固定下来的并查集模板，带路径压缩和按大小合并。

struct DSU { vector<int> fa, sz; DSU(int n) { fa.resize(n + 1); sz.resize(n + 1, 1); for (int i = 1; i <= n; i++) fa[i] = i; } int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); fa[y] = x; sz[x] += sz[y]; } bool same(int x, int y) { return find(x) == find(y); } };

几个设计上的选择说一下：

• 下标从 1 开始还是从 0 开始？模板题的节点编号通常从 1 开始，所以我在构造函数里开n + 1大小的数组，循环也从 1 到 n。如果你要处理从 0 编号的数据，改成循环到 n 即可。别小看这个细节，我见过有人题目里元素编号从 1 开始，他初始化时却只循环到i < n，结果永远少了最后一个节点。
• sz初始化为 1，因为一开始每个节点单独成集合，大小就是 1。只有根节点的sz有意义，非根节点的sz在合并后不会再被读取。
• same单独写成函数，虽然在模板题里可以并到主逻辑里，但抽象出来后，读代码的人一眼就能看出"这是一个查询操作"。

3.2 D006 的输入输出处理，以及主函数写法

拿常见的模板题格式举例：第一行两个数 n 和 m，表示 n 个点、m 个操作。接下来 m 行，每行三个数 op, x, y。op 为 1 表示合并 x 和 y 所在集合，op 为 2 表示查询 x 和 y 是否在同一集合，需要输出 "Y" 或 "N"。

主函数可以这样写：

int main() { int n, m; scanf("%d%d", &n, &m); DSU dsu(n); while (m--) { int op, x, y; scanf("%d%d%d", &op, &x, &y); if (op == 1) { dsu.unite(x, y); } else { puts(dsu.same(x, y) ? "Y" : "N"); } } return 0; }

这里我特意用了scanf和puts，而不是cin/cout。很多刚接触竞赛的同学不理解为什么总有人爱用 scanf，其实就是一个同步开销的问题。cin默认要和 C 标准 IO 同步，导致输入变慢；如果你更喜欢cin，可以在 main 最开头加一句ios::sync_with_stdio(false); cin.tie(nullptr);，效果和 scanf 差距不大。但像 D006 这种 m 可能到 2e5 甚至更大的题，输入方式的选择就可能决定你是 AC 还是 TLE。

我自己的习惯是：写模板题时直接上scanf，反正代码量也不会多几个字；写工程或脚本时才用cin/cout，因为那时可读性优先。

4. 从模板到实战：并查集的几种高频变体

4.1 统计集合个数与最大集合大小

很多题并不满足于"查询是否连通"，而是要求你求出当前有多少个集合、最大集合有多大。这时候sz数组的作用就体现出来了。

维护集合个数有个简单办法：初始化时令cnt = n，每次unite成功（两个根不同）后cnt--。合并结束后，cnt就是集合数量。最大集合大小则遍历所有fa[i] == i的根节点，取sz[i]的最大值。

这个变体我在做"朋友圈"、"省份数量"这类题时经常用。注意遍历集合大小时，只看根节点就可以了，非根节点的sz是废弃数据，看了反而误导。

4.2 带权并查集：在 find 路径上维护距离

基础并查集只记录"父节点是谁"，带权并查集多记录一条"到父节点的权值"。

以经典的"食物链"为例，我们需要维护三种生物关系，即同类、吃、被吃。可以把每个节点的权值d[x]定义为 x 到fa[x]的距离（模 3），路径压缩时一边找根一边累加距离：

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

这里的关键在于顺序：先递归find(fa[x])，此时d[fa[x]]已经被更新为 fa[x] 到根的距离，然后再累加给 x。如果把这个顺序搞反，权值就会算错。这类题目的难点不在模板本身，而在推合并时的权值公式。我的建议是先在纸上画一棵小树，把合并前后的权值关系写出来，再写代码，不要硬记公式。

4.3 可撤销并查集：为什么路径压缩不能回滚

有时候题目要求"撤销上一次合并"，比如离线处理动态连通性问题。这时的并查集就不能用路径压缩了，因为路径压缩改变了树的父子关系，撤销时无法还原现场。

可撤销并查集的做法是：只用按大小合并，不压缩路径；每次合并时把被修改的fa和sz记录到一个栈里。撤销时从栈里弹出并恢复。

void unite(int x, int y) { x = find(x); y = find(y); if (sz[x] < sz[y]) swap(x, y); stk.push({y, fa[y]}); stk.push({x, sz[x]}); fa[y] = x; sz[x] += sz[y]; } void rollback() { fa[stk.top().idx] = stk.top().val; stk.pop(); sz[stk.top().idx] = stk.top().val; stk.pop(); }

注意这里find不能路径压缩，不然栈里记录的fa[y]就不足以恢复整条路径。这个"记录现场-操作-回滚"的思路，也是离线分治、CDQ 分治等高级算法的基础。

4.4 并查集在 Kruskal 最小生成树里的角色

Kruskal 算法每次选一条最短边，尝试把它加入生成树。关键判断是"边的两个端点是否已经连通"，如果已经连通，加入这条边就会成环。这个"是否连通"的查询和"把边加入后连通两个集合"的合并，正好是并查集的主场。

sort(edges, edges + m, cmp); long long ans = 0; for (int i = 0; i < m; i++) { int u = edges[i].u, v = edges[i].v, w = edges[i].w; if (dsu.same(u, v)) continue; dsu.unite(u, v); ans += w; }

没有并查集的时候，每选一条边可能要做一次 DFS/BFS 判断连通性，整体复杂度直接高一个量级。并查集把这里的查询做到了近似 O(1)，Kruskal 的复杂度就只剩排序的 O(m log m) 了。这也是我认为并查集最"值钱"的应用之一。

5. 卡了我一晚上的坑：D006 上的完整排查链路

5.1 现象：样例通过，提交后超时

当时我在 D006 上提交的第一版，本地样例怎么跑都对，但一提交就是红色 TLE。一开始我以为是 OJ 评测机问题，重新交了一次还是超时，这才意识到代码里一定有隐藏的低效点。

我的第一反应是输入太慢。那时候我刚从 cin 切到 scanf，改完之后再交，还是超时。于是我开始怀疑是find的实现有问题——回看代码，发现自己写的确实是最朴素的while写法，完全没有路径压缩。也就是说，如果数据故意构造了一棵深树，每次查询都会沿着链走到底，m 次操作最坏就是 O(nm)，不超时才怪。

5.2 排查过程：从递归爆栈到合并方向错误

加上路径压缩后，我满以为能 AC，结果又交了一次，出来的还是 TLE，而且这次我注意到程序可能不是慢，是栈溢出崩溃。因为我用的是递归版find，如果树深度过大，递归层数可能超过系统栈限制。

于是我再改成迭代版find，同时把unite从"无脑fa[rx] = ry"改成按大小合并。改到这一步，我内心以为问题全解决了。但提交仍是 WA，不是 TLE。这时候我意识到问题已经不在性能上，而在逻辑上。

我打印了中间状态，发现unite里我写的是：

fa[find(x)] = find(y); sz[find(x)] += sz[find(y)];

这个写法看着没问题，但执行顺序上埋了个雷：第一句执行完后，find(y)的结果可能已经被合并到find(x)下面，第二次再调find(x)时，找到的根可能已经变了；更关键的是，sz[find(x)] += sz[find(y)]里两次find的返回值可能指向同一个根，导致集合大小被莫名翻倍。

5.3 修复方式与最终结论

修复方法就是前面模板里写的：先把x和y的根分别取出来存成变量，后续所有操作都基于这两个根变量，不再重复调用find。

x = find(x); y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); fa[y] = x; sz[x] += sz[y];

最后这一版终于 AC。回头看这次排查，最值得记住的不是某个具体 bug，而是"样例通过 ≠ 正确"这个教训。模板题的数据通常不毒，样例更是一切正常，但你的代码要过的是评测机的完整数据，所以在写模板时就要把两种优化、根变量缓存、输入输出这些细节一次性做好，而不是靠数据放水。

这里再多说一句调试技巧：并查集出问题时，我习惯写一个短函数，打印fa[1..n]的当前值和所有根节点对应的sz，在每次操作后输出一次。很多时候 bug 不用分析，看几轮数组变化就能定位。这个方法在本地调试 D006 时帮了我大忙。

6. 把模板内化成自己的工具：我的练习顺序与选题思路

6.1 不要盲目手写模板，先理解每一步存在的原因

有些经验帖说"模板要手写二十遍"，我对这个说法保留意见。如果是应付面试，手写一遍到三遍确实能形成肌肉记忆；但如果要应对竞赛里各种变体，光会默写模板远远不够。你必须知道哪一行是干嘛的、删掉它会发生什么、换一种写法又会影响什么。

我推荐的套路是这样：

• 第一遍：不看任何资料，自己写一个能过的模板题版本，哪怕很朴素。
• 第二遍：把路径压缩加上，理解fa[x] = find(fa[x])的递归过程。
• 第三遍：加上按大小合并，并且回答一个问题：如果两个根相同，为什么要直接 return？
• 之后：做三道不同类型的题，分别用到连通块计数、Kruskal、带权并查集，让模板在不同场景下"变形"。

这样下来，你掌握的不是一段代码，而是一种"看到集合合并与查询，就想用并查集"的直觉。

6.2 适合不同阶段的题目类型与思考方向

结合 D006 这个起点，我按难度整理了一条练习路径，每类题解决一个不同的"为什么"。

选这些题时有一个原则：每道题都要比上一道多做一件你不熟悉的事。如果只是反复刷同一种模板题，你练的只是手速，而不是思维。我自己就在"反集"上吃过亏，第一次做"关押罪犯"的时候完全没想到可以把"敌人"建在一个虚拟集合里，后来理解了i + n表示"与 i 不同类"这种映射，再看这类题就豁然开朗了。

6.3 一个小习惯：把并查集封装成结构体，别写在 main 里裸打

因为 D006 是模板题，代码很短，很多人就随手写在 main 函数里。但等你做了几道进阶题后就会知道，并查集经常要作为一个数据结构被反复调用，封装成结构体/类之后，视觉上清爽，复用也方便，还能避免全局变量名冲突。

我自己的模板从最初的十几行裸代码，慢慢演变成现在带find、unite、same、size四个方法的完整结构体，中间改过很多次，都是根据具体题目的需求一点点加进去的。这也算我刷题路上留下的一个"模板演进"记录吧。

最后分享一个非常实用的小技巧：在本地调试时，给find加一层计数日志，统计它在一次运行中被调用了多少次。如果find的调用次数远远大于操作数，说明你的代码可能在循环里反复 find 同一个东西，这就是一个优化信号。我在写 D006 的排查过程中就是靠这个发现代码里存在大量重复查询的。并查集本身已经很高效了，但前提是你要以正确的方式使用它——先把根存下来，再去做判断和合并，这个好习惯比任何模板都重要。