CSP-S 提高级 · CSP 2025 提高级第一轮 第 5 题

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

这题考拓扑排序的数量性质。拿到题先想：拓扑排序是把 DAG 线性化，只要存在‘自由点’（入度为 0 的点），顺序就能换，数量就会爆炸。别被 n-m 这种线性关系忽悠，孤立点都能排 n! 种，直接选 D。

最容易掉进 A 的坑，以为 DAG 拓扑序唯一，其实只有全序图才唯一；其次是 B，把 n 当成上限，忽略了阶乘级增长；还有 C，死记 n-m 这种线性公式，完全没考虑图结构对自由点数量的影响。

考点定位

图论中的拓扑排序计数问题，属于 CSP 提高级常考概念辨析。

概念拆解

DAG（有向无环图）的拓扑排序，本质是找一个线性序列，让所有边 u→v 都满足 u 在 v 前面。只要图里存在至少一个入度为 0 的“自由点”，我们就有选择：先排它，或者等别的点排完再排它，顺序就能变。

命题人怎么挖坑

这道题就是考你对“拓扑序唯一性”的直觉。命题人爱用极端例子反杀：

• 选项 A 说“只有 1 种”，这只有在图是全序（任意两点间都有边，形成一条链）时才成立，一般 DAG 绝不可能唯一。
• 选项 B 说“最多 n 种”，这是把 n 当成上限，却忘了阶乘爆炸：哪怕全是孤立点（0 条边），n 个点也能排 n! 种，远超 n。
• 选项 C 试图搞个 n-m 的线性公式，听起来像“边越多越受限”，但拓扑序数量跟边数是指数级关系，不是线性减法。

思考心法

拿到题先想：图里有没有自由点？有就有选择，数量立刻>1。再想极端情况：孤立点图、链状图、随机图，分别能排几种？你会发现，只要不是全序，数量就可能巨大，甚至没有简单闭式公式（这是#P-complete 问题）。

避坑指南

• 别被“拓扑序唯一”的片面记忆误导，那是全序图的特例。
• 别拿 n 当上限，阶乘级增长才是常态。
• 别死记 n-m，边数多反而可能让自由点更多（比如稀疏图）。

考频与趋势

拓扑排序在题库共考过 8 题，覆盖 4 个级别（2009-2025），其中 CSP 提高级占了 3 题，NOIP 提高组初赛 3 题，NOIP 普及组初赛 1 题，CSP 入门级 1 题。逐年看，2023 年考了 3 题，2025 年又考了 1 题，说明这个考点在近年仍有热度，尤其是提高级和初赛。

预测

基于现有数据，拓扑排序计数这类概念辨析题仍会出现在 CSP 提高级和 NOIP 提高组初赛中，可能继续以“单选挖坑”形式出现，用极端例子（孤立点、全序图）测试你对唯一性和阶乘级增长的直觉。暂无足够依据预测未来具体年份或题型变化，但这类题目属于基础中的基础，大概率会反复考。

综上，A、B、C 三个具体选项都站不住脚，正确答案只能是 D。