Изменения

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

Рассмотрим пару вершин ''<tex>s'' </tex> и ''<tex>t''</tex>.Если вершины ''<tex>s'' </tex> и ''<tex>t'' </tex> взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.Теперь докажем, что если ''<tex>s'' </tex> и ''<tex>t'' </tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть ''<tex>r'' </tex> - корень этого дерева. Тогда ''<tex>s'' </tex> достижима из ''<tex>r''</tex>, из чего следует, что в обратном графе ''r'' <tex>s</tex> достижима из ''<tex>s''</tex>. Но ''<tex>r'' </tex> имеет большее время окончания обработки <tex>f[r] </tex> > <tex> f[s]</tex>, из чего следует что в обратном графе существует путь из ''<tex>r'' </tex> в ''<tex>s''</tex>. Тогда в исходном графе существуют пути как из ''<tex>s'' </tex> в ''<tex>r''</tex>, так и из ''<tex>r'' </tex> в ''<tex>s''</tex>, т.е. ''<tex>r'' </tex> и ''<tex>s'' </tex> сильно связаны. Те же рассуждения доказывают, что ''<tex>t'' </tex> и ''<tex>r'' </tex> сильно связаны, из чего следует что ''<tex>t'' </tex> и ''<tex>s'' </tex> также сильно связаны.