下列关于拓扑排序的说法中，正确的是（ ）。

Ⅰ．顶点数大于 1 的强连通图不能进行拓扑排序 Ⅱ．在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧 ⟨a,b⟩ Ⅲ．若有向无环图的拓扑序列唯一，则可以唯一确定该图

A. Ⅰ和Ⅱ B. Ⅰ、Ⅱ和Ⅲ C. 仅Ⅰ D. Ⅰ和Ⅲ

[tag_link]

正确答案：C

结论

C 正确。

推导

陈述Ⅰ正确：顶点数大于 1 的强连通图含环。陈述Ⅱ错误：a→x→b 时 a 在 b 前但无直接弧。陈述Ⅲ错误：图一仅有 a→b→c，图二还有 a→c，两图唯一拓扑序列都为 a,b,c。组合选项 A 包含Ⅰ、Ⅱ，B 包含Ⅰ、Ⅱ、Ⅲ，C 仅包含Ⅰ，D 包含Ⅰ、Ⅲ；因此只有选项 C 仅包含Ⅰ这一正确陈述。

易错点

拓扑序列表达偏序约束，不能反推出全部边，更不能唯一确定图。