看到这道题的第一眼我就笑了。题名叫“永远在一起”还带了感叹号给人一种“这怕不是个字符串匹配或者括号序列题”的感觉。实际点开题面发现它是一道非常纯粹的并查集入门题出在 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(nm)。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. 代码实现从暴力到能 AC3.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 访问到没有初始化的节点直接输出 0debug 一下午。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”和“稳过”的关键。这道题里最常见的情况是n1m0。只有一个小朋友他不需要和任何人在一起答案应该是 0。用代码跑一遍components1输出 0正确。有孤立点比如 n5只给 (1,2) 和 (3,4)5 号小朋友谁都不认识。components 最后是 3输出 2正确。孤立点也要算一个连通块这也是为什么初始化 componentsn 而不是统计到的点数。重复关系比如输入两次 (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 吃 BB 吃 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 里没有判断 ab 就减 components。如果输入有重复关系components 会多减答案偏小。所以“先判根相同再合并”这个顺序不能乱。6.3 给新手的几点建议如果你是刚开始接触并查集的新人我建议你按以下顺序练习先写朴素的 find 和 unite理解递归过程再加上路径压缩再加上按大小合并最后把统计连通块数量的方法练熟。不要一上来就背板子而是要学会自己推导为什么路径压缩能提速为什么小的往大的合并只有理解了原理遇到变式你才不慌。还有一点题解里的代码看着短但你自己必须在本地编译器上亲手敲一遍、调试一遍、测试几组边界数据。OI 的学习没有捷径手辛辛苦苦 AC 一道题比看十道题解都有用。“永远在一起”这道题就是很好的起点。我到现在还记得第一次用并查集 AC 这道题时的那种爽快感原来让所有人“在一起”只需要一个数组和几行代码。数据结构从来不冰冷它只是用另一种方式帮你把故事里的承诺变成现实。