🏷️ 知识点：完成时间

用 DFS 算法遍历一个无环有向图，并在 DFS 算法退栈返回时输出相应的顶点，则输出的顶点序列是（ ）。

A. 逆拓扑有序 B. 拓扑有序 C. 无序的 D. 无法确定

正确答案：A

结论

A。退栈时输出的完成时间序列是逆拓扑序。

推导

对任意边 u→v，DFS 必须先完成后继 v，才可能完成 u，因此 v 的完成时间早于 u。按完成时间从先到后输出时，后继在前、前驱在后，正是拓扑序的逆序。

易错点

B 是把完成时间序列与其逆序混淆；C、D 忽略了无环条件下完成时间对每条边的严格约束。