题目

给定如下有向图，该图的拓扑有序序列的个数是( )。

错因

B

漏看了 C → D 这条边。少这条边后，B 出栈时 C 和 D 同时入度归零，可以先 C 后 D 也可以先 D 后 C，序列数翻倍变成 2。出错的根本原因是没有完整建立邻接关系——遇到拓扑题，第一步必须逐边核对入度，漏一条都会让序列数翻倍。

C

漏看了多条边导致同时多个候选。例如同时漏掉 C → D 和 D → E，使得 B 出栈后 C, D 都入度 0 → 选 C 还是 D 是 2 种；之后 E 又能在某些时刻和别的结点并列。组合起来得到 3 种序列。本质和 B 的错因相同：邻接关系建得不全。

D

几乎所有"约束边"都漏看。把图当成只剩树骨架的弱约束 DAG，每一步都有多个候选，得到 4 种或更多序列。这种错误通常发生在没仔细看图、靠直觉估计的情况下。

总解析

思路：拓扑序列个数 = "Kahn 算法每一步候选集大小"的乘积。每步如果只有一个零入度结点，序列被唯一确定；如果有 个，则该步贡献 倍。最终拓扑序列总数 = 各步候选数连乘。

第一步：算所有结点的初始入度。

结点	入边来源	入度
A	（无）	0
B	A	1
C	B	1
D	B, C	2
E	D	1
F	A, B, D, E	4

第二步：Kahn 算法逐步删点。

步	当前入度 0 的结点	选中输出	删边后入度变化
1		A	B → 0，F → 3
2		B	C → 0，D → 1，F → 2
3		C	D → 0
4		D	E → 0，F → 1
5		E	F → 0
6		F	（结束）

关键观察：每一步零入度集合都只有 1 个元素，没有任何分叉点。所以序列唯一：

拓扑有序序列总数 = 。

为什么唯一：本图所有结点构成一条"链状骨架"——A 必须先于 B（A→B），B 必须先于 C（B→C），C 必须先于 D（C→D），D 必须先于 E（D→E），E 必须先于 F（E→F）。这条链已经把 6 个结点的相对顺序完全约束死，其他 A→F、B→D、B→F、D→F 都是"加强约束"，不会带来新的合法顺序。

最终答案是 A（1）。

核对法：拓扑序列唯一 ⟺ 图中存在一条包含所有结点的有向哈密顿路径（每步都存在唯一零入度结点）。本题 A→B→C→D→E→F 恰好就是这条路径。