CSP-S 2023 第一轮 第13题：如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使

题目

如图是一张包含 $6$ 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 $6$ 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

选项

• A. $1$
• B. $2$
• C. $3$
• D. $4$

答案

C

题解

选 C，$3$ 条。

有向图能进行拓扑排序的充要条件是：图中没有有向环。

图中唯一的有向环为： \[ 1\to3\to4\to1 \]

因此，只要删除这个环上的任意一条边，就能消除环，使整个图可以进行拓扑排序。这三条边分别是：

• $1\to3$
• $3\to4$
• $4\to1$

删除其他边都不能破坏这个环，所以候选边共有 $3$ 条。