寻找强连接组件？

Question

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

但是，所有这些算法都要求图的顶点按减去后值（顶点剩下的时间）排序。常见的排序算法如Mergesort需要O（n log n）时间。

因此如何做这些算法设法完成线性时间定位的强连接组件，如果后值需要O排序顶点列表（N log n）的时间？

Answer 1

由于“时间”（测量后值的类型）作为时间的函数（深度优先搜索程序执行的步骤的数量）是单调非降低的，所以可以将每个节点附加到在遍历离开它后立即列表。在遍历结束时，列表按排序顺序排列。另外，由于后值是多项式上界的整数，所以在一些机器模型上，可以使用例如线性时间对它们进行排序。基数排序。