Я не могу понять, как работает алгоритм сильно связанного компонента

Question

Алгоритм сильносвязанного компонента из моей книги:

сильно соединенный-компонент (G)

1. вызовите DFS(G) для вычисления времени окончания f[u] для каждой вершины u
2. вычислить транспонирование (G)
3. вызовите DFS(Transpose(G)), но в главном цикле DFS рассмотрите вершины в порядке убывания f[u] (как вычислено в строке 1)
4. выведите вершины каждого дерева в лесу глубины первый шага 3 как отдельный компонент со строгой связью

Я не очень понимаю, как работает строка 4, как алгоритм создает лес из DFS на транспонированном графе. Я понимаю, почему оба раза звонить в DFS.

Спасибо за любую помощь.

Answer 1

Основной цикл DFS вызывает рекурсивную вспомогательную функцию для каждой вершины, чтобы исследовать вершины, достижимые из этой вершины. "Дерево" здесь - это множество вершин, недавно посещенных одним из этих рекурсивных вызовов. Вспомогательная функция должна быть модифицирована, чтобы создать этот набор, который является сильным компонентом, когда он не пуст.