14
правок
Изменения
→Алгоритм
==Алгоритм==
Данная задачи решается с помощью поиска в глубину в 3 этапа:
#Построить обратный граф<tex>H</tex> с обратными (инвертированными) рёбрами #Выполнить в обратном графе <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - время окончания обработки вершины <tex>u</tex>
#Выполнить поиск глубину в <tex>G</tex>, перебирая вершины во внешнем цикле в порядке убывания <tex>f[u]</tex>
Полученные на 3-ем этапе деревья поиска в глубину будут являться компонентами сильной связности графа <tex>G</tex>.<br>
Так как компоненты сильной связности исходного <tex>G</tex> и обратного <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - на обратном<tex>H</tex>.
===Доказательство===
Рассмотрим пару вершин <tex>s</tex> и <tex>t</tex>.
Если вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы, то они обязательно будут находиться в одном дереве поиска в глубину, поскольку, когда просматривается первая из них, вторая остаётся непосещённой и достижимой из первой и будет просмотрена, прежде чем завершится рекурсивный вызов из корня.<br>
Теперь докажем, что если <tex>s</tex> и <tex>t</tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть <tex>r</tex> - корень этого дерева. Тогда <tex>s</tex> достижима из <tex>r</tex>, из чего следует, что в обратном инвертированном графе <tex>r</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>s</tex> с большим временем оканчания окончания обработки <tex>f[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> также сильно связаны.
==Пример реализации==
