14
правок
Изменения
→Алгоритм
#Выполнить в обратном графе поиск в глубину и найти <tex>f[u]</tex> - время окончания обработки вершины <tex>u</tex>
#Выполнить поиск глубину в <tex>G</tex>, перебирая вершины во внешнем цикле в порядке убывания <tex>f[u]</tex>
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
Так как компоненты сильной связности исходного и обратного графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - на обратном.
===Доказательство===
