扫一眼 USACO 的题单看到 Learning Languages 这个标题很容易觉得它是模拟题——学语言嘛可能就是个字符串匹配或者模拟录入的事。实际做一遍就知道这题压根不考语言考的是图论里的连通分量而且解法极其典型属于那种学会一道就能秒杀一片的题。P3026 这题在 USACO 2011 年 11 月赛季里算入门难度但对于刚接触并查集、刚学会把现实问题抽象成图的人来说它的价值比很多难题都大。这题解决的问题很直白农场里 N 头牛M 种语言每头牛会其中若干种。两头牛如果有共同语言可以直接交流如果没有共同语言还可以靠别的牛当翻译间接交流。问最少让几头牛多学一门语言才能让所有牛都能互相交流。适合谁做正在刷并查集、学图论建模、准备 USACO Bronze/Silver 或者 NOIP 入门组的选手。我当年刷这题时最大的收获不是会了并查集模板而是弄明白了一个道理很多最少操作几次的问题最后都落在有几个连通块上。1. 先看清楚题这题目到底想让你干什么1.1 表面是学语言本质是连通性题面设定很农场风有 N 头牛M 种语言每头牛会 K 门语言。两头牛能直接交流当且仅当它们至少有一种共同语言。如果没有共同语言还可以通过别的牛中转——比如 A 会汉语B 会汉语和英语C 会英语那 A 和 C 虽然语言完全没交集但通过 B 就能搭上线。这个间接交流是解题的关键信号。它意味着交流关系不是看两两之间有没有共同语言而是看整个关系网能不能通过中间人传递。翻译成图论语言这就是连通性把每个元素看成点把能建立联系看成边只要两个点在同一个连通块里它们就能互相到达。题目允许的操作是每次选一头牛让它额外学一门它不会的语言。问最少操作几次能让所有牛都处在同一个连通块里。注意这里不是让每头牛都去学其他所有语言而是用最少的新增联系把所有分散的群体串起来。我第一次看到这题时第一反应是建一张牛与牛的邻接矩阵然后跑 BFS 判断连通性。后来发现没必要因为答案只取决于连通块的数量和每个块内部长什么样完全无关。这就是典型的连通分量计数题。1.2 输入输出格式与样例精讲先看输入格式数据很规整第一行两个整数 N 和 M表示牛的数量和语言总数。接下来 N 行第 i 行第一个数是 K表示第 i 头牛会 K 门语言后面跟着 K 个语言编号。输出一个整数即最少需要让几头牛学习新语言。拿样例来说3 3 2 1 2 1 3 1 2三头牛三种语言。牛 1 会说语言 1 和 2牛 2 只会语言 3牛 3 会说语言 2。画一下关系牛 1 和牛 3 都懂语言 2所以它们直接能聊天。牛 2 只会语言 3既不能直接跟牛 1 聊也不能直接跟牛 3 聊。再看间接交流牛 1 和牛 3 都没学过语言 3所以没人能帮牛 2 翻译牛 2 是完全孤立的。场上其实有两拨牛{牛 1, 牛 3} 是一拨{牛 2} 是一拨。要让所有牛互通最简单的办法是让牛 2 学语言 2学会之后它就能直接和牛 1、牛 3 交流答案就是 1。让牛 2 学语言 1 也可以只要让它进入另一个群体会的语言集合就行。多品一下这个例子会发现答案根本不关心具体让哪头牛学哪门语言只关心场上互相隔绝的牛群一共有几个。如果有 k 个牛群把第 1 个和第 2 个连起来再把第 2 个和第 3 个连起来……连成一条链只需要 k-1 次。这个推导是整个题目的核心后面我会详细证明。2. 怎么想到用并查集问题的传递性2.1 交流的传递性等价于图的连通性提到传递性和集合合并大多数搞过竞赛的人第一反应都是并查集。并查集这个数据结构说穿了就干两件事快速判断两个元素是否在同一个集合里快速合并两个集合。它不擅长处理路径具体怎么走但它恰恰擅长处理到底在不在一个圈子里这种问题。把问题抽象成无向图节点分成两类一类是牛一类是语言。每头牛和它会说的每一种语言之间连一条无向边。这样一来牛 A 和牛 B 能不能交流就等价于在这个图里 A 和 B 是否在同一个连通分量里。为什么这个转化是合法的因为交流的本质就是路径。牛 A - 共同语言 L1 - 牛 B - 共同语言 L2 - 牛 C这样一条路径上相邻节点之间要么是牛和它会的语言要么是语言和会它的牛这就是我们建的边。有路径就代表信息能传递没路径就是彻底隔绝。即使中间绕了七八头牛只要有一条路径就能完成间接交流。这个建模思想值得记下来当问题里出现两类实体、且关系是某类实体属于另一类实体的时候优先考虑把它们放在同一个图里做连通块分析。语言和牛、人和技能、城市和航线都是这样的关系。2.2 两种建图方式优缺点对比我刷题的时候见过两种主流写法都能过但思路略有差异。这里都拿出来对比方便你选一种更合自己口味的。方法一只对语言建并查集。每读入一头牛如果它说的语言不止一门就把它会的所有语言合并进同一个集合。处理完之后统计有牛会说的语言一共有几个连通块。设这个数量为 ans答案就是 ans - 1。方法二牛和语言一起建并查集。给每头牛分配一个编号比如 1 到 N给每种语言分配另一段编号比如 N1 到 NM。读入牛 i 会说语言 x就把 i 和 x 对应的节点合并。最后统计至少包含一头牛的连通分量个数 cnt答案 cnt - 1。两种方法本质完全一样只是视角不同。方法一代码更短但统计时容易漏掉哪些语言是有效的这个判断方法二更直观每一个节点都有明确的含义不容易乱。我个人的建议是新手优先用方法二因为思路不容易出错调试时也方便打印连通分量里的成员。等彻底理解之后再换成方法一写起来会更快。对比项方法一只对语言建图方法二牛和语言混合建图节点含义只有语言节点牛节点 语言节点代码长度较短略长统计注意点要过滤掉没有牛说的语言要过滤掉没有牛的连通分量适合人群熟悉建模后再用新手首选思路直观空间占用较小稍大但本题范围无所谓3. 核心实现代码一步一步来3.1 基础并查集模板先把最基本的并查集模板写出来这个模板包含了 find 和 unite 两个核心操作。#include bits/stdc.h using namespace std; const int MAXN 1005; int fa[MAXN * 2]; // 牛和语言一起编号最多 N M 个节点 int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; // 路径压缩 x fa[x]; } return x; } void unite(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; }数组开 MAXN * 2是因为牛和语言共用一套编号。如果只对语言建并查集开到 M 5 就够了。有些朋友喜欢用递归版 find遇到链特别深的时候可能会有递归栈压力但本题数据范围 N、M 最大只有 1000 左右递归完全没问题。真正需要注意的是路径压缩一定要写否则最坏情况下并查集的查找复杂度会退化到 O(n)整体效率就被拖垮了。路径压缩的原理并不复杂每次查找时顺手把路径上所有节点直接挂到根节点下面下次再查就是一步到位。3.2 读入与合并把牛和语言的关系连起来关键在读入部分。我约定牛的编号从 1 到 N语言的编号做偏移变成 N1 到 NM。比如语言 1 对应的节点是 N1语言 M 对应 NM。int main() { int n, m; cin n m; for (int i 1; i n m; i) fa[i] i; for (int i 1; i n; i) { int k; cin k; while (k--) { int x; cin x; unite(i, n x); // 牛 i 和语言 x 连边 } } // 统计部分后面补上 }为什么是牛 i 和每一门语言合并而不是语言之间互相合并因为我们在用并查集模拟无向图牛 i 和语言 a 之间有边牛 i 和语言 b 之间也有边那么 a 和 b 自然通过牛 i 被连到同一个集合里。这正好对应一头牛会说多门语言时这些语言之间是可以相互翻译的关系。如果 K 是 0说明这头牛一门语言都不会它自己会成为一个孤独的连通分量统计时要算进去。所以 K 为 0 的情况不需要特殊处理只要保证后面的统计逻辑包含了所有牛节点。3.3 统计连通块个数别把没有牛的孤立语言算进去这是全题最容易错的一步我在这里翻过车。按照方法二我们建了 N M 个节点但并非所有节点都是活跃的。语言节点如果没有任何牛会说它就是一个孤立点绝不能算进答案。统计时核心思路是先找出所有集合的根节点再检查每个根节点所在的集合里有没有牛。代码可以这样写vectorint roots; vectorbool has_cow(n m 1, false); // 先给每头牛打标记它所在的集合里有牛 for (int i 1; i n; i) { has_cow[find(i)] true; } // 收集所有根节点 for (int i 1; i n m; i) { if (find(i) i) roots.push_back(i); } int cnt 0; for (int r : roots) { if (has_cow[r]) cnt; } cout cnt - 1 \n;这里的顺序其实可以互换。先标记 has_cow 再收集 roots或者先收集 roots 再标记 has_cow结果一样。关键点是 has_cow 必须用 find(i) 的返回值做下标因为一头牛的根节点可能经过多次合并后不再是它自己。有朋友可能会问能不能直接在遍历节点时统计比如写 if (fa[i] i has_cow[i]) cnt。当然可以但前提是你已经先完整跑了一遍 has_cow 标记。否则你边遍历边标记边统计很容易漏掉那些根节点还没被创建的集合。分两步走逻辑清楚不容易出错。3.4 完整 AC 代码把前面的部分拼起来得到一版可以直接提交的代码#include bits/stdc.h using namespace std; const int MAXN 1005; int fa[MAXN * 2]; int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; } void unite(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 1; i n m; i) fa[i] i; for (int i 1; i n; i) { int k; cin k; for (int j 0; j k; j) { int x; cin x; unite(i, n x); } } vectorint roots; vectorbool has_cow(n m 1, false); for (int i 1; i n; i) { has_cow[find(i)] true; } for (int i 1; i n m; i) { if (find(i) i) roots.push_back(i); } int cnt 0; for (int r : roots) { if (has_cow[r]) cnt; } cout cnt - 1 \n; return 0; }这段代码的时间复杂度是 O((N M 总语言数) * α(N M))其中 α 是反阿克曼函数在题目数据范围下可以当作常数。N 和 M 最多 1000总语言数也不大所以跑起来毫无压力。3.5 另一种实现只对语言建并查集方法一代码更短这里也贴出来给想对比的朋友。它的思路是把所有被某头牛说过的语言合并到同一个集合里最后统计这些语言一共占据多少个连通块。#include bits/stdc.h using namespace std; const int MAXM 1005; int fa[MAXM]; bool used[MAXM]; int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; } void unite(int a, int b) { int ra find(a), rb find(b); if (ra ! rb) fa[ra] rb; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 1; i m; i) fa[i] i; int first_lang -1; for (int i 1; i n; i) { int k; cin k; int pre -1; for (int j 0; j k; j) { int x; cin x; used[x] true; if (pre ! -1) unite(pre, x); pre x; if (first_lang -1) first_lang x; } } if (first_lang -1) { // 所有牛都不说话每头牛都要学一门语言答案 n cout n \n; return 0; } int cnt 0; for (int i 1; i m; i) { if (used[i] find(i) i) cnt; } cout cnt - 1 \n; return 0; }这段代码有一个额外处理的边界如果所有牛的 K 都是 0那所有牛各自都是孤立的每头牛都需要学一门新语言答案就是 n。这个分支在方法二里自然会被统计逻辑覆盖在方法一里需要单独判断所以两个版本各有利弊。4. 踩过的坑这些细节不注意就是 WA4.1 统计连通块时的有牛判断这题最阴间的点就是统计答案的方式。我第一次写这题时直接统计了所有节点的连通分量个数然后减一结果一跑样例第二组就炸了。为什么因为只要某个语言编号没被任何牛提到它就会在并查集里占一个孤立集合白白多算一个连通分量。举个例子有 3 头牛、5 种语言但所有牛只会说语言 1。如果直接统计并查集里所有根节点会发现语言 2、3、4、5 各自都是孤立点算出来连通分量有 5 个答案 4但实际答案是 0因为三头牛早就通过语言 1 连在一起了。所以统计时一定要问自己一句这个集合里真的有牛吗没有牛的集合对答案毫无贡献。这个教训延伸到所有节点包含两类实体的题目里都适用过滤时要想清楚什么才算有效节点。4.2 编号混用把牛当语言把语言当牛我自己犯过的一个低级错误是读入牛 i 会说语言 x 时不小心写成 unite(i, x)牛的编号和语言编号直接混在一个体系里。当 N 和 M 范围接近时语言 1 和牛 1 被当成同一个节点整个并查集就乱了。解决办法很简单要么给语言节点加偏移量像方法二那样统一用 n x 作为语言节点编号要么在建图之前就想清楚两套编号的映射关系。我建议在代码注释里写清楚牛1 到 N语言N1 到 NM避免后来看代码时自己也分不清。4.3 输入里 K 很大但语言不存在的误解题目说了语言总数是 M但输入里某头牛的 K 可能等于 0或者某些语言编号从头到尾没出现过。很多新手会默认编了 1 到 M 的语言就一定有人用这是错的。比如 N2、M100两头牛都会语言 1那么连通分量只有一个答案 0。但如果你统计所有语言节点的连通块会数出 99 个孤立语言节点直接爆炸。再次强调统计前必须用是否被使用或是否有牛关联来过滤。4.4 并查集路径压缩对统计的真实影响路径压缩本身不会影响统计结果的正确性但它会影响你用什么方式去统计。如果你在合并之后、统计之前没有对每个节点重新调用 find(i)那么 fa[i] 可能不是最终的根节点。比如某节点 i 的父节点是 j而 j 后来又挂到了 k 下面此时 fa[i] j 不是根但 find(i) k 才是根。所以统计根节点列表时一定要用 find(i) i 而不是 fa[i] i其实两者在这道题里都可以因为初始化时 fa[i] i只要合并操作后根节点的 fa[root] 仍然指向自己。但为了保险起见我习惯统一写成 find(i) i因为 find 过程会顺便做路径压缩让后续操作更快。4.5 边界情况的处理把这题的边界全列出来对照检查N1无论几门语言所有牛已经能交流答案 0。所有牛的 K0每头牛都得学一门语言答案 N。M 很大但只有一种语言出现答案 0。每头牛只会一种语言且都不同答案 N-1。这些边界不一定会出现在测试数据里但自己造数据验证代码时它们是很好的检查点。5. 解题之外这类最少连线题的通法5.1 从连通分量到答案的推导为什么答案是连通分量数减一而不是其他数这值得认真推一遍。假设场上有 k 个互相不可达的牛群每个牛群是一个包含至少一头牛的连通分量。一次操作选择任意一头牛让它学一门它不会的语言。这门语言如果属于另一个牛群那么这头牛所在的牛群和那个牛群就会因为共享同一门语言而合并成一个更大的牛群。如果学的是一门全新语言暂时不会减少牛群数量但这种情况显然不是最优选择。于是问题变成了有 k 个集合每次操作可以合并两个集合问最少几次能让所有集合合并成一个。每次操作让集合总数减一从 k 到 1 必然经过 k-1 次。k-1 次一定可行少于 k-1 次一定不够所以答案就是 k-1。这个推导还揭示了一个重要事实答案不依赖于图的具体形态只依赖于连通分量数量。所以不管图长成什么样只要连通块数一样答案就一样。这也是为什么用并查集而不是 BFS 逐点判断的原因——我们只需要块数不需要路径细节。5.2 变式与扩展换个皮你还认识吗这类题在竞赛里换壳特别常见举几个例子n 个城市m 条航线问最少新建几条航线能让所有城市连通。这就是无向图连通分量数减一。n 个人m 条好友关系问最少加几条好友关系能让所有人都在一个圈子里。同上。n 台机器m 根网线问最少加几根网线能让所有机器互通。同上。更复杂的版本会在节点种类上做文章比如两类节点、一类节点只能连接特定另一类节点就像这题的牛和语言。核心套路都是建模 - 求连通分量数 - 输出分量数减一。建模的关键是看出哪些关系构成边。语言题里的边是牛-语言好友题里的边是人-人城市题里的边是城市-航线本质没有区别。我建议刷题时多做一步拿到题目背景先不急着写代码把关系提取成图然后问自己三个问题——节点是什么、边是什么、目标是什么。三个问题一答大部分题的解法就浮出水面了。5.3 复杂度与编程技巧最后聊一下编程层面的小技巧。这题 N 和 M 都很小代码怎么写都能过但如果数据范围放到 1e5就要注意几件事不要开二维数组存牛-语言关系会爆内存。用并查集合并是 O(总边数) 的非常省。统计连通块时不要用 unordered_set 存根节点再转 vector直接遍历所有节点收集根就行。读入用 cin 配 ios::sync_with_stdio(false) 足够不用手写快读。如果语言编号范围很大比如 1e9可以用 map 做离散化把出现过的语言映射到连续的 1 到 tot再做并查集。这道题我前前后后写过三遍每一遍都有新体会。第一遍用 BFS 染色第二遍用牛和语言混合并查集第三遍才写出干净的语言并查集版本。回头看最值钱的不是代码本身而是看破背景、提取关系、统计块数这个思考路径。最后再分享一个小习惯每次 AC 之后我都会故意把数据改成边界情况再跑一遍比如所有牛都不会语言、所有牛都会同一门语言、语言总数远大于实际出现数。这个小习惯帮我避开了至少三成以上的低级 WA建议你也试试。