Дает ли алгоритм SCC Тарьяна топологический вид SCC?

Я изучал SCC и алгоритмы о них, и я видел, что люди почти всегда упоминают, что алгоритм Косараджу находит SCC и также упорядочивает их в (обратном) топологическом виде.

Мой вопрос: разве алгоритм Тарьяна также не находит (обращенную) топологическую сортировку? Я обнаружил, что это не упоминается (по крайней мере, откуда я читал, кроме Википедии).

Я думал об этом и имел смысл. Когда tarjans_dfs вызывается на некотором узле u, все SCC, которые достижимы из u, будут найдены до SCC u. Я ошибся?

Википедия говорит, что действительно находит это:

«Хотя нет ничего особенного в порядке узлов в каждом сильно связанном компоненте, одно полезное свойство алгоритма состоит в том, что ни один сильно связанный компонент не будет идентифицирован ни перед одним из его преемников. Следовательно, порядок, в котором сильно связанные компоненты идентифицированный образует обратную топологическую разновидность DAG, образованной сильно связанными компонентами ».

Это моя идея, или гораздо более известно, что алгоритм Косараджу находит топологический порядок, чем тот факт, что Тарьян также делает это?

Ответы на вопрос(3)

Ваш ответ на вопрос