CSP-J 入门级 · CSP 2023 入门级第一轮 第 12 题

考虑一个有向无环图，该图包含 $4$ 条有向边：$(1,2),(1,3),(2,4)$ 和 $(3,4)$。以下哪个选项是这个有向无环图的一个有效的拓扑排序?

这题考拓扑排序，拿到图先看边的方向，只要记住'每条边 u→v 都要求 u 在 v 前面'，把四个选项里的数字顺序跟这四条边一一比对，哪个全对就是答案。

最容易栽跟头的是把'1→2'看成'2 必须在 1 前'，或者只盯着入度为 0 的点以为随便排就行。其实拓扑排序不是让你重新排节点，而是验证给定的序列里，四条有向边的起点是否都在终点前面。很多人还会把'1→3'和'3→4'搞混，以为 3 可以插在 4 前面就万事大吉，却忘了 1 必须在 3 前面，检查时往往漏看一条边就选错。

考点一句话：拓扑排序的本质是‘对有向无环图做线性排列，使得每条边 u→v 都满足 u 在 v 之前’。本题不给入度计算过程，直接让你从四个序列里挑出符合这个规则的。

图的结构：四条边分别是 1→2、1→3、2→4、3→4。画个草图就能看出 1 是唯一起点，4 是唯一起点，中间 2 和 3 都紧跟着 1，最后汇聚到 4。

逐一验证选项（这是解题最稳的套路，别省步）：

• A. 4,2,3,1：第一条边 1→2 就崩了，因为 4 排在最前，1 在最后，1 不可能在 2 前面。直接排除。
• B. 1,2,3,4：1 在最前，2 在 1 后，3 在 1 后，4 在最后。四条边都满足：1→2（1 在 2 前）✓，1→3（1 在 3 前）✓，2→4（2 在 4 前）✓，3→4（3 在 4 前）✓。完美。
• C. 1,2,4,3：前两条边没问题，但看 3→4，这里 4 跑在 3 前面了，违反规则。排除。
• D. 2,1,3,4：1→2 这条边要求 1 在 2 前，可序列里 2 排在 1 前面，直接挂掉。

心算技巧：不用真的算入度，只要记住‘每条边 u→v 都要求 u 在 v 前面’，把四个选项里的数字顺序跟这四条边一一比对，哪个全对就是答案。

易错提醒：很多人会下意识觉得'1 是起点所以 1 必须第一’，其实拓扑排序允许有多个起点，但本题里 1 确实是唯一的入度为 0 的点，所以它必须排第一。更常见的坑是只看前两条边就以为 B 和 C 都对，忘了回头检查 3→4 那条边。

考频与趋势：拓扑排序在题库里一共考过 8 题，覆盖 4 个考试级别（2009-2025）。逐年分布：2009 年 1 题、2010 年 2 题、2017 年 1 题、2023 年 3 题、2025 年 1 题。分赛事：NOIP 提高组初赛 3 题、CSP 提高级 3 题、NOIP 普及组初赛 1 题、CSP 入门级 1 题。从数据看，2023 年考了 3 题，是近年小高峰，之后 2025 年回落为 1 题，整体属于低频但稳定的考点，尤其在 CSP 入门级和 NOIP 普及组初赛里偶尔出现。

未来预测：基于现有 8 题的分布，CSP 入门级和 NOIP 普及组初赛各 1 题，其余集中在提高级和普及组提高级，暂无足够依据预测未来会突然增加高频考查，但考虑到 2023 年的小高峰，未来几年在入门级和普及组中仍可能保持 1-2 题的考查强度。