CSP-S 2026 第一轮 第 11 题：一张有向图缩点后得到的有向无环图含 6 个顶点

题目

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

选项

• A. 7
• B. 6
• C. 4
• D. 3

答案

C

题解

答案是 C．4。

缩点后，每个顶点代表原图的一个强连通分量。要让原图强连通，就要让缩点后的 DAG 强连通。

对于含至少两个顶点的 DAG，有一个结论： \[ \text{最少添加边数}=\max(\text{入度为 0 的顶点数},\text{出度为 0 的顶点数})。 \]

理解这个结论：

• 入度为 0 的 3 个点，每个都需要新增一条入边，否则其他点无法到达它。
• 出度为 0 的 4 个点，每个都需要新增一条出边，否则它无法到达其他点。
• 一条新增边可以同时作为一个点的出边和另一个点的入边。通过适当安排，取两者的最大值就足够。

因此，最少需要添加 \[ \boxed{\max(3,4)=4\text{ 条}}。 \]

注意：\(3+4>6\) 并不矛盾，因为孤立点的入度、出度都为 0，会被两边重复计数。