尧图网站开发 
刷 USACO 的题刷久了你会发现很多题其实就差一层窗户纸。P3026 [USACO11OPEN] Learning Languages S 就是这样一道典型的“连通分量”入门题题面围绕着农场里的牛和语言绕来绕去但一旦你把模型想清楚代码量可以短到只有几十行。这道题在洛谷上是绿题难度考的知识点非常干净——并查集求连通分量以及一个“分量数减一”的贪心结论。我这里把完整的思考过程、建模方式、两种实现和踩坑记录都整理出来希望能帮正在刷 USACO 和洛谷图论基础题的朋友一步到位。先说清楚题目到底在讲什么农场里有 N 头牛一共 M 种语言。每头牛会若干种语言两头牛只要会说同一种语言就能直接交流就算没有共同语言也可以通过中间会多种语言的牛做翻译间接交流。FJ 想让所有牛最终都能互相交流他可以花一节课教任意一头牛任意一门语言。问题就是最少需要多少节课。这题适合谁来参考准备 USACO Bronze/Silver 的选手、刚开始学并查集但还没做过“连通分量类”题目的同学都可以拿它当模板题。它考察的不是什么冷门算法而是你能不能把一个生活场景翻译成图论模型。把模型想通了后面一大堆类似的“连通块合并”题都能顺手解决。1. 先把题意拆明白语言不通到底卡在哪1.1 一个农场一头牛和一堆语言题目输入格式很直白第一行两个整数 N 和 M接下来 N 行每行先给一个整数 K表示这头牛会几种语言然后跟着 K 个语言编号。注意 K 可以是 0也就是一头牛可能一门语言都不会。我随便构造一组数据来跑通思路5 5 2 1 2 1 2 2 3 4 1 5 0这组数据的意思是牛 1 会语言 1、语言 2牛 2 只会语言 2牛 3 会语言 3、语言 4牛 4 只会语言 5牛 5 什么语言都不会。肉眼扫一遍牛 1 和牛 2 通过语言 2 可以直接对话。牛 3 的两种语言都和牛 1、牛 2 没关系所以牛 3 暂时是孤立的一坨。牛 4 也一样。牛 5 是彻底的“语言白痴”谁的话都听不懂也没人听得懂它。这种情况下至少要几节课答案是 3。你可以这样操作先教牛 5 学会语言 2那牛 5 就归到牛 1、牛 2 这一组了接着教牛 3 学会语言 2牛 3 这一组也并进来再教牛 4 学会语言 2全都并完了。三节课刚好把四坨“阵营”串成一条线。这个“阵营”就是后面要反复说的连通分量。1.2 直接说话、翻译链和连通性为什么说它是一道连通性题目因为“间接交流”在图论里就是“路径”的意思。把能交流的关系看成边牛是点那么两头牛能交流等价于它们之间存在一条路径。举一个最常见的翻译链牛 A 只会英语牛 C 只会法语牛 B 既会英语又会法语。A 和 C 不能直接说但 A 找 B、B 再找 C三个人就能形成一条完整的交流链。在图里就是 A——B——C 这样一条路径A 和 C 属于同一个连通块。反过来如果一头牛完全不会语言它和外界没有任何一条路径它自己就是孤立块。只要它没学会任何一门语言它就不可能被并进任何连通块里来。所以在正式建模之前脑子里要先装下这个概念题目问的“让所有牛能互相交流”等价于“把所有包含牛的连通分量合并成一个”问的“最少几节课”等价于“最少加几条边能把所有连通分量连通”。这个翻译一出来题目难度就降了一大半。2. 核心建模把牛和语言都当成节点2.1 只用牛建图为什么很麻烦有一个直觉做法是如果两头牛有共同语言就在这两头牛之间连一条边然后数牛组成的连通块。听着简单但实现起来非常别扭。你要先读入所有牛的语言列表然后两两枚举牛再对每两头牛做一次语言集合求交集。复杂度往少了说也是 O(N^2 * K)N 一大直接没法看。更关键的是“翻译链”这个信息在只连牛的图里反而会被隐藏。比如牛 A 会语言 1牛 B 会语言 1 和语言 2牛 C 会语言 2。如果只连牛A-B 有一条边B-C 有一条边那 A 和 C 也能连通这没问题。但如果语言关系更深一些比如 A 会语言 1B 会语言 1、2C 会语言 2、3D 会语言 3你依然得靠语言集合才能判断 A 和 D 能不能交流。用牛直接连边也不是不行但构造边的时候要做的集合判断很多代码写起来又长又容易漏。这时候你应该想到一个非常自然的优化为什么不让语言本身也变成一个“点”2.2 二分图思路语言就是中转站把每头牛也看成一个点把每种语言也看成一个点。牛如果会说某种语言就在这头牛和这个语言之间连一条无向边。这样建出来的图是一个二分图一边是牛一边是语言边只存在于牛和语言之间。这个模型妙在哪妙在共同语言可以自动“搭桥”。两头牛会不会说同一种语言不需要你去判断只要它们都连着同一个语言点那么经过这个语言点它们就自动处于同一个连通块里。翻译链更不用说牛 A 连接语言 1语言 1 连接牛 B牛 B 又连接语言 2语言 2 连接牛 C于是 A、B、C 都在一个连通块里。你什么都不用额外做连通性自己会传播。也就是说语言点在图上充当“中间节点”的角色它把我们原本需要人工判断的“间接关系”转化成了图上的“路径”。2.3 一节课在图上是加一条边现在再看“上课”这个操作。FJ 教牛 Bessie 一门新语言 x翻译成图论语言就是在牛 Bessie 对应的点和语言 x 对应的点之间添加一条新边。这个对应关系非常关键。因为我们最终的答案要求是“所有牛在一个连通块”而图论里有一个基本事实在一个无向图里每添加一条边如果连接的是两个不同的连通分量那么连通分量数减少 1如果连接的是同一个分量内部的两个点连通分量数不变。我们要让分量数最终变成 1所以每一步都应该尽量做“跨分量连边”的操作。一条边最多只能让分量数减 1这是不可能突破的下限。2.4 最少课数 连通分量数 - 1假设我们统计完建好的初始图发现包含牛的连通分量一共有 c 个。因为每次加一条边最多只能把分量数减 1所以要把 c 个分量合并成 1 个分量至少要 c - 1 条边也就是至少要 c - 1 节课。这个下界能不能达到可以。每一次操作都这样选从两个不同的连通分量里各找一头牛然后让其中一头牛去学另一头牛会的某门语言。由于它们原来属于不同分量这条新边必然跨越两个分量加了之后两个分量立刻合并成一个。这样重复 c - 1 次最终所有分量都会合并成一个。有人可能会问如果某个分量里只剩下一头什么语言都不会的牛怎么办好办另一头牛随便会一门语言让这头“白丁牛”去学那门语言它也就能并进大部队了。和上面的操作逻辑完全一致。所以结论成立最少课程数就是图中包含牛的连通分量个数减一。这里要特别强调“包含牛”三个字,因为有的语言点可能会独立存在吗实际上不会因为语言点只有被牛连接才会出现但“只有语言集合而没有任何牛”的空块在算法上要避免统计进去。所以正确的统计口径是只看牛点所在的分量语言点只承担连通作用不单独算分量。3. 用并查集把上面的模型变成代码3.1 为什么选并查集建模是二分图那统计连通分量用什么工具最直接的是 DFS/BFS 遍历整张图遍历一次就能数出连通块数量。但还有一个更贴合这题的经典工具并查集。并查集擅长处理的就是“动态连接”和“查询是否连通”。我们这题建图过程其实就是不断把牛节点和语言节点连起来的过程用并查集维护“哪些点已经连通”再合适不过。代码量小常数小也不容易写出玄学 bug。3.2 节点编号方案牛有 N 个语言有 M 个要放在同一个并查集里必须先统一编号。我习惯这样定牛的编号用 1 到 N语言的编号用 N1 到 NM。这样牛和语言绝对不会冲突。如果你输入的牛编号和语言编号都从 1 开始直接塞进同一个并查集就会出现灾难性的错误——牛 1 和语言 1 会被当成同一个东西。并查集数组大小开 N M 5 就够了多加几个是为了防止数组越界这种低级问题。3.3 读入与合并读入第 i 头牛的信息时依次读入它会的每个语言编号 lang然后把牛 i 和语言节点 (N lang) 合并到同一个集合里。注意一点一头牛如果会多个语言它必须分别和每个语言都连边这样它才能起到“翻译桥梁”的作用。比如牛 i 会语言 1 和语言 2你需要 union(i, N1) 和 union(i, N2)做完之后语言 1、牛 i、语言 2 就自动跑到同一个连通块里了。这头牛以后就能帮语言 1 的牛和语言 2 的牛传话。如果一头牛的 K 是 0什么都不做它就保持孤独状态后面统计的时候它也会自成一个连通块完全符合题意。核心合并代码就这几行for (int i 1; i n; i) { int k; cin k; for (int j 0; j k; j) { int lang; cin lang; unite(i, n lang); } }3.4 统计并输出合并做完之后图就建好了。现在数一数有多少个“包含牛的连通分量”。做法很简单遍历每头牛 1 到 N对每头牛执行 find(i)得到它所在连通块的根节点塞进一个 set 里。因为 set 会自动去重最后 set 的大小就是包含牛的连通分量数 c。为什么不遍历语言节点因为有些语言节点虽然存在但它的连通块里可能只包含语言而没有牛仔细想想其实不可能——语言节点只有被牛的边连到才会被合并进某个根如果某语言节点从来没被任何牛读过它根本不会出现在程序逻辑里。但为了安全起见统计时只针对牛节点这样即使有孤立语言节点存在于并查集数组中也不会影响答案。最后输出 set.size() - 1就是最少需要多少节课。setint roots; for (int i 1; i n; i) { roots.insert(find(i)); } cout (int)roots.size() - 1 \n;3.5 完整参考代码下面是一份可以直接提交的 C 代码并查集用的是递归写法数据范围很小不用担心爆栈。如果你平时习惯迭代版 find也可以直接替换。#include bits/stdc.h using namespace std; vectorint fa; int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void unite(int a, int b) { a find(a); b find(b); if (a ! b) fa[a] b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; fa.resize(n m 5); 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 lang; cin lang; unite(i, n lang); } } setint roots; for (int i 1; i n; i) { roots.insert(find(i)); } cout (int)roots.size() - 1 \n; return 0; }用前面那组样例跑一遍牛 1 和牛 2 通过语言 2 连成一个分量牛 3 和语言 3、4 成一个分量牛 4 和语言 5 成一个分量牛 5 只跟自己成一个分量。set 里有 4 个根输出 3完美符合手动推出来的答案。4. 不用牛节点的语言集合做法4.1 思路简述只合并语言有人会想牛节点可不可以不建毕竟最后答案是“课数”我们能不能只维护语言之间的关系确实可以。基本思路是读入一头牛的语言时如果它只会一门语言那这门语言暂时作为一个孤立集合如果它会多门语言就说明这头牛能在这些语言之间做翻译所以这些语言应该被合并到同一个集合里。换句话说“语言集合”就代表一个可以互相交流的牛群。所有会说这些语言中任意一种的牛都自动属于这个语言集合对应的连通块。4.2 核心代码长这样每头牛读入时记下第一个语言 first从第二个语言开始依次把它和 first 合并int zero 0; for (int i 1; i n; i) { int k; cin k; if (k 0) { zero; continue; } int first; cin first; for (int j 1; j k; j) { int lang; cin lang; unite(first, lang); } }统计时对所有语言节点求根放入 set数量记为 s。但这里有个必须单拎出来的东西不会任何语言的牛。它的数量记为 zero。每一头零语言牛自成一个独立连通块所以总连通块数应该是 s zero。最终答案是 s zero - 1。setint roots; for (int lang 1; lang m; lang) { roots.insert(find(lang)); } int s (int)roots.size(); cout s zero - 1 \n;这个公式看着简单但很容易忘掉 zero 那一项。如果直接输出 s - 1遇到牛 5 这种零语言牛就会算错。4.3 两种方法的等价性从数学上讲两种方法统计出来的连通分量数量一定一致。第一种方法中牛节点连接多个语言节点等价于把这几个语言节点“捆绑”到同一个连通块第二种方法直接用语言节点的合并来模拟这个捆绑过程。第一种方法会对每头牛执行若干次 union第二种方法对每头牛执行 k-1 次 union。由于并查集的合并操作满足结合性最终语言节点之间的连通关系是一样的。差别只在于第一种方法多建了 N 个牛节点空间稍大第二种方法必须额外处理零语言牛否则容易翻车。4.4 两种做法怎么选我个人的建议是平时训练和比赛都用第一种“牛 语言”二分图建模因为它最贴近问题本质边界情况被天然吃掉不容易错。第二种方法代码稍微短一点但“zero”这个隐藏变量太容易踩坑了。而且面试、讲题、写题解的时候第一种讲出来别人更容易听懂。对比项牛 语言二分图只合并语言集合节点总数N MM零语言牛处理自动计入需要单独统计代码可读性高模型直观略绕但不长出错风险低容易漏 zero推荐程度强烈推荐可作为理解辅助5. 实战中的坑与排查技巧5.1 零语言牛的坑这是最常见的错误。很多新手统计完语言集合数量之后直接输出语言集合数减一完全没意识到不会语言的牛也是一个独立的连通分量。举例两头牛牛 1 会语言 1牛 2 什么都不会。语言集合数 s 1如果输出 s - 1 0答案就错了。实际上牛 2 听不懂任何话必须花一节课教它一门语言正确答案是 1。用第一种二分图建模就不会犯这个错因为牛 2 的根会被单独计算进去。5.2 统计所有节点导致多算有些人统计的时候图省事把语言节点也一起塞进 setfor (int i 1; i n m; i) roots.insert(find(i));这个写法在这个题里通常不会错因为根本没有语言会在没有牛连接的情况下出现在图中——输入里给出的语言一定属于某头牛所以语言节点不会脱离牛形成独立空块。但这是一种危险的坏习惯。万一题目变了一下输入里包含一些“农场里存在但没有任何牛会说”的语言编号你统计全部节点就会把这些空语言集合也算成分量答案直接偏大。老老实实只统计牛节点永远最稳。5.3 数组开小或编号越界并查集数组只开 N 5然后自信地去访问 n lang这是非常经典的 RE。语言编号最大是 M那你最远要访问到 N M。所以数组至少开 N M 5。用 vector 动态分配也可以但别忘了把 1 到 NM 的父节点初始化为自己。还有个细节编程时语言编号输入是从 1 开始映射成并查集下标时要 n lang不是 lang。如果忘了加 n牛点和语言点直接打架find 出来的根全是乱的。5.4 递归栈和路径压缩本题 N、M 都很小递归 find 完全没压力。但如果哪天你把这套模型用到 N、M 到几十万的题目里注意递归深度问题。解决办法很简单改成非递归 find或者把递归改成循环加路径压缩。路径压缩一定要做不然反复 find 会退化。int find(int x) { int root x; while (fa[root] ! root) root fa[root]; while (x ! root) { int nxt fa[x]; fa[x] root; x nxt; } return root; }这个非递归版在数据大的时候更稳建议收藏。5.5 一个容易忽略的等价情况如果所有牛都会语言并且所有语言都通过牛的翻译链连通了那答案就是 0。比如牛 1 会语言 1、2牛 2 会语言 2、3牛 3 会语言 3。三头牛已经连通set 大小为 1输出 1 - 1 0。这个边界很容易让人不敢输出 0但请放心这是合法答案。6. 从这道题里提炼出通用套路6.1 看见“间接连通”就想到连通分量“A 能通过 B 联系到 C”“所有点都要能互相到达”“问最少建几条路才能全部连通”这些描述本质都是同一个模型无向图连通分量。识别出这个套路之后核心工作就是建模和数连通块。常见问法有两种。一种问“最少加几条边让全图连通”答案就是连通分量数减一就像这题。另一种问“删掉哪些边会让图变成两个连通块”那就是桥和割边的问题了属于更高一级的考点。6.2 为什么很多“最小连接”题的答案都是 c - 1严格证明前面已经讲过了我再从另一个角度帮大家加深记忆。假设当前图里有 c 个连通分量目标是变成 1 个。每次加一条跨分量的边可以让两个分量合并分量数减 1每次加一条分量内部的边分量数不变。要减少 c - 1 次至少需要 c - 1 条有效边。而 c - 1 条边一定足够你只需要把各个分量排成一串依次连接相邻两个就能把所有分量串成一个整体。这其实和“一棵树有 n 个节点需要 n - 1 条边”是同一个直觉。把每个连通分量压缩成一个点最后你要把这 c 个“缩点”全部连通成一棵树树上需要的边数正好是 c - 1。6.3 相似题目与扩展方向拿这套模型去刷洛谷你会发现自己突然会了很多题。入门级的 P3367 就是纯并查集模板P1536 村村通问的是“还要修几条路才能让所有村连通”几乎就是这题去掉语言外壳的版本答案同样是连通块数减一P1195 口袋的天空问的是“连成 K 个最小生成树需要多少代价”核心也在连通块合并只不过多了边权要用最小生成树的思路。如果将来遇到更难的变式比如“每门课有固定费用求最小总费用”那就要把本题的贪心结论升级成最小生成树或者 Kruskal 重构树但“先求连通分量再合并”这个骨架是始终不变的。最后说点个人做题体会。我最初做这道题的时候犯的错误就是没有把牛和语言分开编号导致牛 1 和语言 1 共用一个并查集节点样例都过不了。后来改成“牛节点用 1 到 N语言节点用 N1 到 NM”之后整个人豁然开朗。另一处觉得特别值得记住的教训是不要看到“会语言”的牛才去处理那些 K 0 的牛恰恰是容易丢分的边界它们也必须算作独立的连通分量。这个细节在考场上可能比算法本身更致命。如果你也想练这道题建议先别急着看代码自己手动构造几组数据尤其构造一组有零语言牛的、一组所有牛已经能互相沟通的体会一下答案分别是多少。把这两组边界跑明白这道题你就真正吃透了。 
刷 USACO 的题刷久了你会发现很多题其实就差一层窗户纸。P3026 [USACO11OPEN] Learning Languages S 就是这样一道典型的“连通分量”入门题题面围绕着农场里的牛和语言绕来绕去但一旦你把模型想清楚代码量可以短到只有几十行。这道题在洛谷上是绿题难度考的知识点非常干净——并查集求连通分量以及一个“分量数减一”的贪心结论。我这里把完整的思考过程、建模方式、两种实现和踩坑记录都整理出来希望能帮正在刷 USACO 和洛谷图论基础题的朋友一步到位。先说清楚题目到底在讲什么农场里有 N 头牛一共 M 种语言。每头牛会若干种语言两头牛只要会说同一种语言就能直接交流就算没有共同语言也可以通过中间会多种语言的牛做翻译间接交流。FJ 想让所有牛最终都能互相交流他可以花一节课教任意一头牛任意一门语言。问题就是最少需要多少节课。这题适合谁来参考准备 USACO Bronze/Silver 的选手、刚开始学并查集但还没做过“连通分量类”题目的同学都可以拿它当模板题。它考察的不是什么冷门算法而是你能不能把一个生活场景翻译成图论模型。把模型想通了后面一大堆类似的“连通块合并”题都能顺手解决。1. 先把题意拆明白语言不通到底卡在哪1.1 一个农场一头牛和一堆语言题目输入格式很直白第一行两个整数 N 和 M接下来 N 行每行先给一个整数 K表示这头牛会几种语言然后跟着 K 个语言编号。注意 K 可以是 0也就是一头牛可能一门语言都不会。我随便构造一组数据来跑通思路5 5 2 1 2 1 2 2 3 4 1 5 0这组数据的意思是牛 1 会语言 1、语言 2牛 2 只会语言 2牛 3 会语言 3、语言 4牛 4 只会语言 5牛 5 什么语言都不会。肉眼扫一遍牛 1 和牛 2 通过语言 2 可以直接对话。牛 3 的两种语言都和牛 1、牛 2 没关系所以牛 3 暂时是孤立的一坨。牛 4 也一样。牛 5 是彻底的“语言白痴”谁的话都听不懂也没人听得懂它。这种情况下至少要几节课答案是 3。你可以这样操作先教牛 5 学会语言 2那牛 5 就归到牛 1、牛 2 这一组了接着教牛 3 学会语言 2牛 3 这一组也并进来再教牛 4 学会语言 2全都并完了。三节课刚好把四坨“阵营”串成一条线。这个“阵营”就是后面要反复说的连通分量。1.2 直接说话、翻译链和连通性为什么说它是一道连通性题目因为“间接交流”在图论里就是“路径”的意思。把能交流的关系看成边牛是点那么两头牛能交流等价于它们之间存在一条路径。举一个最常见的翻译链牛 A 只会英语牛 C 只会法语牛 B 既会英语又会法语。A 和 C 不能直接说但 A 找 B、B 再找 C三个人就能形成一条完整的交流链。在图里就是 A——B——C 这样一条路径A 和 C 属于同一个连通块。反过来如果一头牛完全不会语言它和外界没有任何一条路径它自己就是孤立块。只要它没学会任何一门语言它就不可能被并进任何连通块里来。所以在正式建模之前脑子里要先装下这个概念题目问的“让所有牛能互相交流”等价于“把所有包含牛的连通分量合并成一个”问的“最少几节课”等价于“最少加几条边能把所有连通分量连通”。这个翻译一出来题目难度就降了一大半。2. 核心建模把牛和语言都当成节点2.1 只用牛建图为什么很麻烦有一个直觉做法是如果两头牛有共同语言就在这两头牛之间连一条边然后数牛组成的连通块。听着简单但实现起来非常别扭。你要先读入所有牛的语言列表然后两两枚举牛再对每两头牛做一次语言集合求交集。复杂度往少了说也是 O(N^2 * K)N 一大直接没法看。更关键的是“翻译链”这个信息在只连牛的图里反而会被隐藏。比如牛 A 会语言 1牛 B 会语言 1 和语言 2牛 C 会语言 2。如果只连牛A-B 有一条边B-C 有一条边那 A 和 C 也能连通这没问题。但如果语言关系更深一些比如 A 会语言 1B 会语言 1、2C 会语言 2、3D 会语言 3你依然得靠语言集合才能判断 A 和 D 能不能交流。用牛直接连边也不是不行但构造边的时候要做的集合判断很多代码写起来又长又容易漏。这时候你应该想到一个非常自然的优化为什么不让语言本身也变成一个“点”2.2 二分图思路语言就是中转站把每头牛也看成一个点把每种语言也看成一个点。牛如果会说某种语言就在这头牛和这个语言之间连一条无向边。这样建出来的图是一个二分图一边是牛一边是语言边只存在于牛和语言之间。这个模型妙在哪妙在共同语言可以自动“搭桥”。两头牛会不会说同一种语言不需要你去判断只要它们都连着同一个语言点那么经过这个语言点它们就自动处于同一个连通块里。翻译链更不用说牛 A 连接语言 1语言 1 连接牛 B牛 B 又连接语言 2语言 2 连接牛 C于是 A、B、C 都在一个连通块里。你什么都不用额外做连通性自己会传播。也就是说语言点在图上充当“中间节点”的角色它把我们原本需要人工判断的“间接关系”转化成了图上的“路径”。2.3 一节课在图上是加一条边现在再看“上课”这个操作。FJ 教牛 Bessie 一门新语言 x翻译成图论语言就是在牛 Bessie 对应的点和语言 x 对应的点之间添加一条新边。这个对应关系非常关键。因为我们最终的答案要求是“所有牛在一个连通块”而图论里有一个基本事实在一个无向图里每添加一条边如果连接的是两个不同的连通分量那么连通分量数减少 1如果连接的是同一个分量内部的两个点连通分量数不变。我们要让分量数最终变成 1所以每一步都应该尽量做“跨分量连边”的操作。一条边最多只能让分量数减 1这是不可能突破的下限。2.4 最少课数 连通分量数 - 1假设我们统计完建好的初始图发现包含牛的连通分量一共有 c 个。因为每次加一条边最多只能把分量数减 1所以要把 c 个分量合并成 1 个分量至少要 c - 1 条边也就是至少要 c - 1 节课。这个下界能不能达到可以。每一次操作都这样选从两个不同的连通分量里各找一头牛然后让其中一头牛去学另一头牛会的某门语言。由于它们原来属于不同分量这条新边必然跨越两个分量加了之后两个分量立刻合并成一个。这样重复 c - 1 次最终所有分量都会合并成一个。有人可能会问如果某个分量里只剩下一头什么语言都不会的牛怎么办好办另一头牛随便会一门语言让这头“白丁牛”去学那门语言它也就能并进大部队了。和上面的操作逻辑完全一致。所以结论成立最少课程数就是图中包含牛的连通分量个数减一。这里要特别强调“包含牛”三个字,因为有的语言点可能会独立存在吗实际上不会因为语言点只有被牛连接才会出现但“只有语言集合而没有任何牛”的空块在算法上要避免统计进去。所以正确的统计口径是只看牛点所在的分量语言点只承担连通作用不单独算分量。3. 用并查集把上面的模型变成代码3.1 为什么选并查集建模是二分图那统计连通分量用什么工具最直接的是 DFS/BFS 遍历整张图遍历一次就能数出连通块数量。但还有一个更贴合这题的经典工具并查集。并查集擅长处理的就是“动态连接”和“查询是否连通”。我们这题建图过程其实就是不断把牛节点和语言节点连起来的过程用并查集维护“哪些点已经连通”再合适不过。代码量小常数小也不容易写出玄学 bug。3.2 节点编号方案牛有 N 个语言有 M 个要放在同一个并查集里必须先统一编号。我习惯这样定牛的编号用 1 到 N语言的编号用 N1 到 NM。这样牛和语言绝对不会冲突。如果你输入的牛编号和语言编号都从 1 开始直接塞进同一个并查集就会出现灾难性的错误——牛 1 和语言 1 会被当成同一个东西。并查集数组大小开 N M 5 就够了多加几个是为了防止数组越界这种低级问题。3.3 读入与合并读入第 i 头牛的信息时依次读入它会的每个语言编号 lang然后把牛 i 和语言节点 (N lang) 合并到同一个集合里。注意一点一头牛如果会多个语言它必须分别和每个语言都连边这样它才能起到“翻译桥梁”的作用。比如牛 i 会语言 1 和语言 2你需要 union(i, N1) 和 union(i, N2)做完之后语言 1、牛 i、语言 2 就自动跑到同一个连通块里了。这头牛以后就能帮语言 1 的牛和语言 2 的牛传话。如果一头牛的 K 是 0什么都不做它就保持孤独状态后面统计的时候它也会自成一个连通块完全符合题意。核心合并代码就这几行for (int i 1; i n; i) { int k; cin k; for (int j 0; j k; j) { int lang; cin lang; unite(i, n lang); } }3.4 统计并输出合并做完之后图就建好了。现在数一数有多少个“包含牛的连通分量”。做法很简单遍历每头牛 1 到 N对每头牛执行 find(i)得到它所在连通块的根节点塞进一个 set 里。因为 set 会自动去重最后 set 的大小就是包含牛的连通分量数 c。为什么不遍历语言节点因为有些语言节点虽然存在但它的连通块里可能只包含语言而没有牛仔细想想其实不可能——语言节点只有被牛的边连到才会被合并进某个根如果某语言节点从来没被任何牛读过它根本不会出现在程序逻辑里。但为了安全起见统计时只针对牛节点这样即使有孤立语言节点存在于并查集数组中也不会影响答案。最后输出 set.size() - 1就是最少需要多少节课。setint roots; for (int i 1; i n; i) { roots.insert(find(i)); } cout (int)roots.size() - 1 \n;3.5 完整参考代码下面是一份可以直接提交的 C 代码并查集用的是递归写法数据范围很小不用担心爆栈。如果你平时习惯迭代版 find也可以直接替换。#include bits/stdc.h using namespace std; vectorint fa; int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void unite(int a, int b) { a find(a); b find(b); if (a ! b) fa[a] b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; fa.resize(n m 5); 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 lang; cin lang; unite(i, n lang); } } setint roots; for (int i 1; i n; i) { roots.insert(find(i)); } cout (int)roots.size() - 1 \n; return 0; }用前面那组样例跑一遍牛 1 和牛 2 通过语言 2 连成一个分量牛 3 和语言 3、4 成一个分量牛 4 和语言 5 成一个分量牛 5 只跟自己成一个分量。set 里有 4 个根输出 3完美符合手动推出来的答案。4. 不用牛节点的语言集合做法4.1 思路简述只合并语言有人会想牛节点可不可以不建毕竟最后答案是“课数”我们能不能只维护语言之间的关系确实可以。基本思路是读入一头牛的语言时如果它只会一门语言那这门语言暂时作为一个孤立集合如果它会多门语言就说明这头牛能在这些语言之间做翻译所以这些语言应该被合并到同一个集合里。换句话说“语言集合”就代表一个可以互相交流的牛群。所有会说这些语言中任意一种的牛都自动属于这个语言集合对应的连通块。4.2 核心代码长这样每头牛读入时记下第一个语言 first从第二个语言开始依次把它和 first 合并int zero 0; for (int i 1; i n; i) { int k; cin k; if (k 0) { zero; continue; } int first; cin first; for (int j 1; j k; j) { int lang; cin lang; unite(first, lang); } }统计时对所有语言节点求根放入 set数量记为 s。但这里有个必须单拎出来的东西不会任何语言的牛。它的数量记为 zero。每一头零语言牛自成一个独立连通块所以总连通块数应该是 s zero。最终答案是 s zero - 1。setint roots; for (int lang 1; lang m; lang) { roots.insert(find(lang)); } int s (int)roots.size(); cout s zero - 1 \n;这个公式看着简单但很容易忘掉 zero 那一项。如果直接输出 s - 1遇到牛 5 这种零语言牛就会算错。4.3 两种方法的等价性从数学上讲两种方法统计出来的连通分量数量一定一致。第一种方法中牛节点连接多个语言节点等价于把这几个语言节点“捆绑”到同一个连通块第二种方法直接用语言节点的合并来模拟这个捆绑过程。第一种方法会对每头牛执行若干次 union第二种方法对每头牛执行 k-1 次 union。由于并查集的合并操作满足结合性最终语言节点之间的连通关系是一样的。差别只在于第一种方法多建了 N 个牛节点空间稍大第二种方法必须额外处理零语言牛否则容易翻车。4.4 两种做法怎么选我个人的建议是平时训练和比赛都用第一种“牛 语言”二分图建模因为它最贴近问题本质边界情况被天然吃掉不容易错。第二种方法代码稍微短一点但“zero”这个隐藏变量太容易踩坑了。而且面试、讲题、写题解的时候第一种讲出来别人更容易听懂。对比项牛 语言二分图只合并语言集合节点总数N MM零语言牛处理自动计入需要单独统计代码可读性高模型直观略绕但不长出错风险低容易漏 zero推荐程度强烈推荐可作为理解辅助5. 实战中的坑与排查技巧5.1 零语言牛的坑这是最常见的错误。很多新手统计完语言集合数量之后直接输出语言集合数减一完全没意识到不会语言的牛也是一个独立的连通分量。举例两头牛牛 1 会语言 1牛 2 什么都不会。语言集合数 s 1如果输出 s - 1 0答案就错了。实际上牛 2 听不懂任何话必须花一节课教它一门语言正确答案是 1。用第一种二分图建模就不会犯这个错因为牛 2 的根会被单独计算进去。5.2 统计所有节点导致多算有些人统计的时候图省事把语言节点也一起塞进 setfor (int i 1; i n m; i) roots.insert(find(i));这个写法在这个题里通常不会错因为根本没有语言会在没有牛连接的情况下出现在图中——输入里给出的语言一定属于某头牛所以语言节点不会脱离牛形成独立空块。但这是一种危险的坏习惯。万一题目变了一下输入里包含一些“农场里存在但没有任何牛会说”的语言编号你统计全部节点就会把这些空语言集合也算成分量答案直接偏大。老老实实只统计牛节点永远最稳。5.3 数组开小或编号越界并查集数组只开 N 5然后自信地去访问 n lang这是非常经典的 RE。语言编号最大是 M那你最远要访问到 N M。所以数组至少开 N M 5。用 vector 动态分配也可以但别忘了把 1 到 NM 的父节点初始化为自己。还有个细节编程时语言编号输入是从 1 开始映射成并查集下标时要 n lang不是 lang。如果忘了加 n牛点和语言点直接打架find 出来的根全是乱的。5.4 递归栈和路径压缩本题 N、M 都很小递归 find 完全没压力。但如果哪天你把这套模型用到 N、M 到几十万的题目里注意递归深度问题。解决办法很简单改成非递归 find或者把递归改成循环加路径压缩。路径压缩一定要做不然反复 find 会退化。int find(int x) { int root x; while (fa[root] ! root) root fa[root]; while (x ! root) { int nxt fa[x]; fa[x] root; x nxt; } return root; }这个非递归版在数据大的时候更稳建议收藏。5.5 一个容易忽略的等价情况如果所有牛都会语言并且所有语言都通过牛的翻译链连通了那答案就是 0。比如牛 1 会语言 1、2牛 2 会语言 2、3牛 3 会语言 3。三头牛已经连通set 大小为 1输出 1 - 1 0。这个边界很容易让人不敢输出 0但请放心这是合法答案。6. 从这道题里提炼出通用套路6.1 看见“间接连通”就想到连通分量“A 能通过 B 联系到 C”“所有点都要能互相到达”“问最少建几条路才能全部连通”这些描述本质都是同一个模型无向图连通分量。识别出这个套路之后核心工作就是建模和数连通块。常见问法有两种。一种问“最少加几条边让全图连通”答案就是连通分量数减一就像这题。另一种问“删掉哪些边会让图变成两个连通块”那就是桥和割边的问题了属于更高一级的考点。6.2 为什么很多“最小连接”题的答案都是 c - 1严格证明前面已经讲过了我再从另一个角度帮大家加深记忆。假设当前图里有 c 个连通分量目标是变成 1 个。每次加一条跨分量的边可以让两个分量合并分量数减 1每次加一条分量内部的边分量数不变。要减少 c - 1 次至少需要 c - 1 条有效边。而 c - 1 条边一定足够你只需要把各个分量排成一串依次连接相邻两个就能把所有分量串成一个整体。这其实和“一棵树有 n 个节点需要 n - 1 条边”是同一个直觉。把每个连通分量压缩成一个点最后你要把这 c 个“缩点”全部连通成一棵树树上需要的边数正好是 c - 1。6.3 相似题目与扩展方向拿这套模型去刷洛谷你会发现自己突然会了很多题。入门级的 P3367 就是纯并查集模板P1536 村村通问的是“还要修几条路才能让所有村连通”几乎就是这题去掉语言外壳的版本答案同样是连通块数减一P1195 口袋的天空问的是“连成 K 个最小生成树需要多少代价”核心也在连通块合并只不过多了边权要用最小生成树的思路。如果将来遇到更难的变式比如“每门课有固定费用求最小总费用”那就要把本题的贪心结论升级成最小生成树或者 Kruskal 重构树但“先求连通分量再合并”这个骨架是始终不变的。最后说点个人做题体会。我最初做这道题的时候犯的错误就是没有把牛和语言分开编号导致牛 1 和语言 1 共用一个并查集节点样例都过不了。后来改成“牛节点用 1 到 N语言节点用 N1 到 NM”之后整个人豁然开朗。另一处觉得特别值得记住的教训是不要看到“会语言”的牛才去处理那些 K 0 的牛恰恰是容易丢分的边界它们也必须算作独立的连通分量。这个细节在考场上可能比算法本身更致命。如果你也想练这道题建议先别急着看代码自己手动构造几组数据尤其构造一组有零语言牛的、一组所有牛已经能互相沟通的体会一下答案分别是多少。把这两组边界跑明白这道题你就真正吃透了。