algorithm - 寻找强连接组件？

Question

我的书定义了一种在线性时间内找到有向图的强连通分量的方法。此外，其他几种寻找强连通分量的算法（即 Tarjan 算法）也能够在线性时间内找到分量。

然而，所有这些算法都要求图的顶点以递减的后值排序（顶点离开的时间）。Mergesort 等常见的排序算法需要 O(n log n) 时间。

因此，如果按post值对顶点列表进行排序需要 O(n log n) 时间，这些算法如何在线性时间内完成对强连通分量的定位？

Answer 1

由于“时间”（用于测量后置值的类型）作为时间（深度优先搜索程序执行的步数）的函数是单调非递减的，因此只需在遍历离开它。在遍历结束时，列表按排序顺序排列。

或者，由于后值是多项式以上的整数，因此在某些机器模型上，可以使用例如基数排序在线性时间对它们进行排序。