CSP-S 提高级 · CSP 2026 提高级第一轮 第 11 题

【单选】一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个、出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。

缩点后是 DAG，要把整张图变成强连通，最少添加的边数 = max(入度为 0 的数目, 出度为 0 的数目)，本题即 max(3, 4) = 4（前提是 SCC 个数 ≥ 2）。

误用"入度 0 数 + 出度 0 数"（得 7，错选 A）；或者把已经强连通的特殊情况套上公式（若整图本身是一个 SCC，答案是 0，公式会给出 1，必须特判）。

解析

本题考查有向图强连通化（缩点成 DAG 后的最小加边数）。

问题的转化

把原图的每个强连通分量缩成一个点后，得到一张有向无环图（DAG）。要让原图变成强连通图，等价于让这张 DAG 强连通，而所需要添加的最少边数只跟 DAG 的"源点/汇点"数量有关：

设入度为 0 的顶点数为 A，出度为 0 的顶点数为 B，则最少添加边数 = max(A, B)（SCC 个数 ≥ 2 时）

直观理解

• 每个"入度 0"的点没人指向它，必须至少有一条边进入；
• 每个"出度 0"的点出不去，必须至少有一条边离开；
• 一条新增边 u → v 可以同时解决一个"入度为 0 的 v"和一个"出度为 0 的 u"，所以能"配对解决"时是 max(A, B)，多余的用环上的边补足（这也是为什么不是简单相等）。

代入本题

• 入度为 0 的点：A = 3
• 出度为 0 的点：B = 4

最少添加边数 = max(3, 4) = 4，选 C。

其他选项为什么错

• A. 7 = 3 + 4：把"配对"关系忽略了，每条边只能解决一个需求；
• B. 6、D. 3：随意取了两者之一或做了错误的配对假设。

必须记住的特判

当整张图只有一个强连通分量时，答案应为 0（已经强连通，不用加边）。此时 A = B = 1，公式 max(A,B) = 1 会给出错误答案——所以做题时先看"缩点后顶点数"，若为 1 则直接答 0。

记忆点

• 强连通判定与缩点、拓扑排序是同一套工具链（Tarjan / Kosaraju）；
• 源点（入度 0）与汇点（出度 0）的配对思想在"最少添边""最少加多少条边能走遍全图"等题里反复出现；
• 补充一个常见变形：若要求"从某个点出发能到达所有点"，则只需从该点连边到所有入度 0 的点，答案就是 A 而不是 max(A,B)。