CSP-S 提高级 · CSP 2023 提高级第一轮 第 13 题

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

这题考拓扑排序与环的判定。图有拓扑序等价于无环（DAG）。题目说原图无拓扑序，说明有环；删一条边后要有拓扑序，就是要删掉能打断所有环的边。拿到图先找环，再找环的公共边，答案就是公共边的数量。

学生最容易犯两个错误：一是把不在环上的边也算进去，以为删了也能让图变 DAG，其实删非环边图里仍有环，拓扑序依然不存在；二是只盯着一个环看，漏掉图中可能存在的其他环，导致以为删了某条边就万事大吉。正确做法是找出图中所有有向环，然后取它们的交集——只有交集中的边才是候选。如果图中只有一个环，那环上的每条边都是候选；如果有多个环，必须删掉同时在所有环上的边才能彻底消除所有环。

这道题考查的是图论中拓扑排序与有向环的关系，属于 CSP 提高级常见的图结构分析题型。命题人喜欢把“拓扑排序存在”这个抽象条件转化为“图中没有有向环”这个直观性质，然后让学生通过删边去破坏环，从而考察对环的识别能力和集合交集思维。拿到这样的题，核心心法是：先确认原图为什么没有拓扑序（一定有环），再思考删一条边后怎么让图变成 DAG（必须打断所有环），最后落实到具体边（一定是所有环的公共边）。计算时，如果只有一个环，环上的每条边都是候选；如果有多个环，只有同时出现在所有环上的边才是候选，因为删其他边至少会留下一个环，拓扑序依然不存在。避坑的关键是别被图里复杂的边干扰，只关注环的结构；也别想当然认为删任意一条边都能解决问题，必须严格验证是否覆盖了所有环。从考频趋势看，拓扑排序在题库中仅考过 8 题，覆盖 4 个考试级别，近年在 CSP 提高级（3 题）和 NOIP 提高组初赛（3 题）中稳定出现，说明这是基础但高频的考点，命题人倾向于用它作为判断图性质或设计算法流程的切入点。基于现有数据，暂无足够依据预测未来具体出题形式，但可以合理推断：未来仍可能以类似“删边使图变为 DAG”的变体出现，或者结合其他图论性质（如连通性、路径计数）综合考查。回到本题，分析图中有向环结构可知，存在三个边同时位于所有环上，删除其中任意一条都能彻底消除所有环，使图变为 DAG，因此候选边共有 3 条，对应选项 C。