私の本では、有向グラフの強連結成分を線形時間で見つける方法を定義しています。さらに、強連結成分を見つけるための他のいくつかのアルゴリズム (つまり、Tarjan のアルゴリズム) も線形時間で成分を見つけることができます。
ただし、これらのアルゴリズムはすべて、ポスト値 (頂点が残っている時間) が減少するようにグラフの頂点を並べ替える必要があります。Mergesort などの一般的な順序付けアルゴリズムは、O(n log n) 時間かかります。
したがって、ポスト値で頂点のリストを並べ替えるのに O(n log n) の時間がかかる場合、これらのアルゴリズムはどのようにして強連結成分の位置を線形時間で完全に特定できるのでしょうか?