看到这道题的第一眼，我就笑了。题名叫“永远在一起”，还带了感叹号，给人一种“这怕不是个字符串匹配或者括号序列题”的感觉。实际点开题面，发现它是一道非常纯粹的并查集入门题，出在 IXOI R1 的 T1 位置，题号 P15445。这种题放在比赛第一题，不是为了难住你，而是为了让你明白：比赛里的浪漫背景，经常只是套着一个算法模型的外衣，剥开之后就是基础中的基础。

题目大意是这样的：有 n 个小朋友，编号从 1 到 n。现在给出 m 条“友谊承诺”，每条承诺包含两个编号 a 和 b，表示小朋友 a 和小朋友 b 必须永远在一起。所谓“在一起”，就是他们最终要属于同一个集合。问你最少还需要补充几条这样的承诺，才能让所有的 n 个小朋友都在同一个集合里？看不懂题没关系，记住这句话：把每个小朋友看成一个点，每条承诺看成一条无向边，“永远在一起”等价于“两个点必须在同一个连通块里”。剩下的，就是并查集的主场了。

1. 题目说了啥：别被“永远在一起”吓到

1.1 把题意翻译成人话

“永远在一起”听起来像童话，但 OI 题面最喜欢干的事就是把简单的模型包装成故事。这里的关键信息只有两个：

• n 个点，初始时谁也不认识谁，每个人单独成一个集合。
• 每次输入一个“承诺”，等价于在 a 和 b 之间连一条边。因为“在一起”是相互的，所以这是一条无向边。

问最少加几条边能让所有点连通。这其实是在问：当前图里有多少个连通块。假设有 k 个连通块，那么想让它们变成一个连通块，至少需要 k-1 条边。只需要把每个连通块当成一个超级点，然后在这 k 个点之间连一条链，就能用恰好 k-1 条边把它们全部串起来。所以答案就是：

当前连通块的数量 - 1

这个结论是从图论里“连通块”的定义直接推出来的，不需要任何高深知识。边可以加在任意两个块之间，哪怕这两块内部没有真实存在的边，也不影响你补一条虚拟关系。题目只问你最少加几条，不关心你怎么加。

1.2 为什么答案是连通块数量减一

很多同学看到“最少”两个字就开始慌，觉得是不是要跑最小生成树，甚至想到了二分答案。实际上这道题根本不需要那么复杂。设当前图有 k 个连通块，为了把所有点连成一个整体，你需要添加的边数至少是 k-1，因为每条新边最多只能让两个连通块合并，k 个块合并成 1 个至少要合并 k-1 次。这个下界是严格的吗？是。你只需要在第 1 个块和第 2 个块之间加一条边，就把它们变成了一个更大的块；再把这个大块和第 3 个块之间加一条边，又合并一次。重复 k-1 次，所有块就都连通了。因此答案就是 k-1。

所以整道题的难点就剩一个：如何快速在线维护动态连通块的数量。这正是并查集（Union-Find / Disjoint Set Union）最擅长的场景。你可以一边读入承诺，一边合并两个集合，同时维护一个计数器记录当前还剩多少个集合，最后输出计数器减一。整个流程行云流水，复杂度几乎可以看成 O(n+m)。

2. 并查集：维护“在一起”关系的数据结构

2.1 并查集是干什么的

并查集是一种用来处理“集合合并”和“查询两个元素是否在同一集合”的数据结构。生活化的理解：每个集合都有一个“老大”（代表元素）。你问一个元素属于哪个集合，就沿着它的“上级”一路向上找，找到老大；你想合并两个集合，就让其中一个集合的老大认另一个老大当老大。这就像找工作时的“背调”：想知道两个人是不是一个团队的，就看看他们的最终老板是不是同一个人。

在这个题里，集合就是“朋友圈”，老大就是朋友圈里的某个代表。每次输入 a、b，我们先分别找到 a 的老大和 b 的老大。如果两个老大一样，说明 a、b 已经在同一朋友圈里，不需要任何操作；如果老大不一样，说明这两个朋友圈目前还没“在一起”，那就让一个老大认另一个当大哥，两个集合正式合并。

2.2 三个基本操作：初始化、查找、合并

并查集的核心只有三个操作，写成模板差不多就是下面这个样子。

初始化：每个点都是自己所在集合的老大。

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 unite(int a, int b) { a = find(a); b = find(b); if (a != b) fa[b] = a; }

这三段代码加起来就是最朴素的并查集。理论上它已经能通过这道题，但数据范围一大，朴素的查找可能会退化成一条链，导致复杂度变成 O(n) 一次查找，整体 O(nm) 直接超时。所以我们需要下面要说的优化。

2.3 时间复杂度的直觉分析

为什么朴素的并查集会慢？假设你每次都把 b 的根接在 a 的根下面，而且恰好每次都让较长的链继续变长，最终会形成一条深度为 n 的链。查找最后一个节点时，要一路走到底，复杂度就是 O(n)。更糟的是，每次查找都走这么深，m 次操作就是 O(nm)。

路径压缩能解决这个问题。简单来说，当你在 find 的过程中找到根之后，顺手把沿途所有节点的父指针直接指向根。这样下一次再找这些节点时，一步就能跳到根。路径压缩+按秩合并的并查集，单次操作均摊复杂度接近 O(1)，准确说是反阿克曼函数级别的，可以认为就是常数。这个结论是计算机科学里著名的“并查集复杂度”分析，竞赛里你只需要记住：它非常快，快到你几乎不用考虑它的极限。

3. 代码实现：从暴力到能 AC

3.1 初始化：每个人都是自己的老大

我先说一个很多新手容易忽略的点：数组下标从 1 开始还是从 0 开始，取决于题目输入的编号范围。这道题小朋友编号是 1 到 n，所以循环从 1 开始。fa[i] 存的是 i 的父亲节点，初始化时让 fa[i] = i，意思是每个点自成一个集合，自己就是根。如果想顺带维护集合大小，就再开一个 sz 数组，初始化为 1。维护大小在“按大小合并”的优化里很有用。

const int MAXN = 100005; int fa[MAXN], sz[MAXN]; for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; }

注意：如果你开了 MAXN 却只初始化到 n，那么输入中出现大于 n 的编号就会越界。题目保证编号合法，但你自己写代码时仍要养成“按实际范围初始化”的习惯。我见过不少同学在为了省事初始化 MAXN 到 100000，实际 n 只有 10，结果后面 find 访问到没有初始化的节点，直接输出 0，debug 一下午。

3.2 查找与合并：带优化的核心代码

查找函数我建议写成递归形式。数据范围在 10^5 级别时，加上路径压缩后递归深度不会太大；但如果你担心栈溢出，或者你的编译器开小栈，可以改成非递归。先看递归版：

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

这里的路径压缩发生在回溯过程中：当你 find(fa[x]) 返回了根 r，就把 fa[x] 改成 r。这样下次再查 x 时，一次就到位。如果你想要更保险的非递归写法，可以参考：

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

非递归版本先找到根，再顺着原路径把沿途每个点的父亲都改成根，并不复杂。两种写法效果一样，选你自己顺手的就行。

合并函数里结合“按大小合并”：

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

为什么要让大的当根？因为把小的树挂到大树上，树的高度增长最慢，最坏情况下树高是 O(log n)。配合路径压缩，整体效率极高。如果你不想维护 sz，也可以维护一个 rank（秩）表示树的深度，按秩合并，效果等价。

3.3 完整代码：直接用这个就能过

把上面的片段拼起来，再处理输入输出，就是能 AC 的完整答案。这里我选择了在每次成功合并时让连通块计数器减一，这样最后不需要再遍历一遍统计，更简洁。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int fa[MAXN], sz[MAXN]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); fa[b] = a; sz[a] += sz[b]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } int components = n; for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); if (find(a) != find(b)) { unite(a, b); components--; } } printf("%d\n", components - 1); return 0; }

这个代码等价于：初始每个小朋友都是独立集合，所以有 n 个连通块。每次读入一对 a、b，如果它们已经在一起，则什么都不做；否则合并两个集合，连通块数量减一。最终 components 就是当前连通块数量，输出 components - 1 就是最少还需要添加的承诺数。

3.4 最后的统计环节：还有没有别的写法

如果你不在主循环里维护 components，也可以最后统一数根的数量。方法是遍历所有点，如果 i 的根就是 i 自己，说明它是一个集合的代表元素，统计一下数量即为连通块数。这样代码的统计逻辑更直观，但多了一次 O(n) 遍历。两种写法都能过，我个人的习惯是在合并时顺手减一，因为这样最终只剩一次输出，不需要再开一个布尔数组标记根。但要注意：components 的初始值必须是 n，而不是 m 或者别的。有些同学会把 components 初始化成 0，然后边读入边加，这会导致答案完全错误。这个坑我踩过，印象很深。

4. 优化与实现细节：别人不会告诉你的坑

4.1 路径压缩的递归与非递归：到底选哪个

递归版 find 简洁漂亮，是绝大多数题解的标准写法。但有个容易被忽略的问题：某些平台的编译栈默认只有几 MB，当并查集在极端数据下退化成一条长链时，如果此时没有按大小合并，只有路径压缩，递归深度可能达到 n（比如你先连续 union 构建出链，再对链尾做查找）。虽然路径压缩之后链会变扁，但递归时的函数调用栈已经深入了 n 层，可能爆栈。

解决思路有两个：一是用按大小合并，保证树高是 O(log n)，递归深度不会太大；二是直接写非递归版本，彻底摆脱栈溢出风险。竞赛场景下，我更推荐递归版+按大小合并的组合，因为它好记、好写、不易错。如果你在做特别大的数据或者参加机试，建议改成非递归版，一劳永逸。

4.2 按大小合并而不是按深度合并

按大小合并的“大小”指的是集合里元素个数。每次合并时，把元素少的集合并到元素多的集合里。这样做能让树高保持在 O(log n) 级别。有人会问，按深度合并不是更直接吗？确实，经典教材里常按秩合并，秩就是树的深度。但秩需要额外维护，而且当路径压缩发生时会改变深度，维护起来稍麻烦。按大小合并的代码更简单，效果一样好，因为集合大小是单调不减的，不会出现深度超过 log n 太多的情况。

你可以这样理解：一个节点所在的树高度每增加一层，它所在集合的大小至少翻倍。初始每个集大小是 1，高度最多为 log2(n)。所以无论怎么合并，树高都不会超过 log n。这个“翻倍论证”是理解按大小合并复杂度的核心，面试时也常被问到。

4.3 输入输出选择：scanf 还是 cin

这道题的 n、m 最大到 10^5 量级，cin 加 ios::sync_with_stdio(false) 也能过。但如果数据增大到 10^6，建议用 scanf 或者快读。注意 cin 和 scanf 不要混用，尤其不要一边关同步一边用 scanf，这样可能会打乱缓冲区状态。我个人的原则是：涉及大数据一律 scanf/printf，既安全又没心理负担。如果想更高端，可以自己写 getchar 快读，但本题没必要。

4.4 边界情况：孤立点、重复关系、自环

边界情况是区分“能 AC”和“稳过”的关键。这道题里最常见的情况是：

• n=1，m=0。只有一个小朋友，他不需要和任何人在一起，答案应该是 0。用代码跑一遍：components=1，输出 0，正确。
• 有孤立点，比如 n=5，只给 (1,2) 和 (3,4)，5 号小朋友谁都不认识。components 最后是 3，输出 2，正确。孤立点也要算一个连通块，这也是为什么初始化 components=n 而不是统计到的点数。
• 重复关系，比如输入两次 (1,2)。第一次合并后第二次 find(a)==find(b)，跳过，不影响答案。
• 自环，比如 (1,1)，一个小朋友和自己永远在一起没有意义。find(1)==find(1)，直接跳过，不影响答案。

这些边界情况不特殊，但它们是 OJ 上“WA 一个点”的最常见来源。很多人样例过了就交，最后挂在这个上面，得不偿失。

5. 从这一题延伸出去：并查集的更多打开方式

5.1 最小生成树里的 Kruskal

并查集最有名的应用其实是 Kruskal 算法。最小生成树问题里，你要把 n 个点用 n-1 条边连起来，且总边权最小。Kruskal 的做法是把所有边按边权从小到大排序，然后依次枚举每条边，如果边连接的两个点不在同一连通块，就选这条边并合并两个集合。这里的“选边”就是一次“在一起”的确认。你可以在 P15445 的基础上把“最少添加几条边”改成“最小边权和是多少”，思路立刻从计数问题变成贪心问题，这就是 Kruskal 的雏形。所以别看这题简单，它给后面很多经典算法打基础。

5.2 带权并查集与“银河英雄传说”

有时候，我们不仅要判断两个元素是否在一个集合里，还想知道它们之间的相对关系。比如食物链问题：A 吃 B，B 吃 C，问两个动物同类还是天敌；再比如银河英雄传说：每条指令把一列战舰接在另一列后面，还要回答任意两艘战舰之间隔了多少战舰。这些都需要在并查集的边上维护权值，也就是“带权并查集”。带权并查集的 find 函数要在路径压缩时同步累加边权，unite 时也要根据关系式算出父亲节点的权值。这个知识点比本题难不少，但思想来自同一个模型：树上的父子关系代表集合成员关系，权值代表“距离”或“偏移量”。

5.3 离线处理、可撤销并查集与启发式合并

再往深走，你会遇到需要支持“撤销合并”的题目。普通并查集合并容易，想撤销难，因为路径压缩破坏了原始树结构。解决办法是在合并时用按秩合并（不路径压缩），并用栈记录每次合并操作的细节，这样可以从顶到底依次退回——也就是“可撤销并查集”。配合分治，还能处理“只有一段时间内存在的边”的问题。这些都是竞赛进阶内容，但根都在这一道“永远在一起”上。学会基础，后面才谈得上扩展。

6. 赛后复盘与个人经验

6.1 拿到题后的第一反应

比赛时我在想，“永远在一起！”会不会考的是字符串？但是看到数据范围是 n、m，以及“一条承诺”这种字眼，就应该立刻转向图论模型。这类经验需要刷题积累：看到“必须在一起”“同一个集合”“至少添加几条边”等等，优先考虑并查集。如果题目加上“权值最小”就去想 Kruskal；如果加上“在线询问两个点是否连通”，就是动态连通性，也常用并查集；如果加上“删除边”，则要考虑离线倒序。

6.2 我在代码里踩过的坑

第一次写这题时，我犯过一个很傻的错误：初始化循环写成了 for (int i = 0; i <= n; i++)，把 fa[0] 也初始化了。题目编号从 1 开始，fa[0] 虽然不会用到，但 components 初始值我写成了 m，导致答案完全不对。后来 debug 才发现。另一个坑是，我在 unite 里没有判断 a==b 就减 components。如果输入有重复关系，components 会多减，答案偏小。所以“先判根相同，再合并”这个顺序不能乱。

6.3 给新手的几点建议

如果你是刚开始接触并查集的新人，我建议你按以下顺序练习：先写朴素的 find 和 unite，理解递归过程；再加上路径压缩；再加上按大小合并；最后把统计连通块数量的方法练熟。不要一上来就背板子，而是要学会自己推导：为什么路径压缩能提速？为什么小的往大的合并？只有理解了原理，遇到变式你才不慌。

还有一点：题解里的代码看着短，但你自己必须在本地编译器上亲手敲一遍、调试一遍、测试几组边界数据。OI 的学习没有捷径，手辛辛苦苦 AC 一道题，比看十道题解都有用。“永远在一起”这道题，就是很好的起点。我到现在还记得第一次用并查集 AC 这道题时的那种爽快感：原来让所有人“在一起”，只需要一个数组和几行代码。数据结构从来不冰冷，它只是用另一种方式，帮你把故事里的承诺变成现实。