CSP-S 2025 第一轮 第5题：对于一个包含 n 个结点和 m 条边的有向无环图（DAG），其拓扑排序的结果有多

题目

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

选项

• A. 只有 $1$ 种
• B. 最多 $n$ 种
• C. 等于 $n - m$ 种
• D. 以上都不对

答案

D

题解

选 D．以上都不对。

拓扑排序要求：对于每条有向边 \(u\to v\)，\(u\) 必须排在 \(v\) 前面。因此，排序的数量取决于图中具体的依赖关系。

例如，取 \(n=3,m=0\)，即 3 个结点之间没有边，任意排列都合法，共有 \[ 3!=6\text{ 种}. \] 这一个例子就能排除所有前三项：

• A 错：有 6 种，不是只有 1 种。
• B 错：\(6>n=3\)。
• C 错：\(6\ne n-m=3\)。

一般来说，含 \(n\) 个结点的 DAG，拓扑排序数量最少为 1（例如所有结点连成一条有向链），最多为 \(n!\)（没有任何边）。