14
правок
Изменения
→Доказательство
Рассмотрим пару вершин <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>sr</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> также сильно связаны.
==Пример реализации==
