Так как компоненты сильной связности <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>r \rightsquigarrow s</tex>, из чего следует, что в инвертированном графе есть путь <tex>s \rightsquigarrow r</tex>. Очевидно, что <tex>f[r]</tex> > <tex>f[s]</tex>, т. к. мы рассматриваем вершины в порядке убывания <tex>f[u]</tex>. Предположим, что пути <tex>s \rightsquigarrow r</tex> в исходном графе нет. Тогда в инвертированном графе нет пути <tex>r \rightsquigarrow s</tex>. Исходя из факта существования в инвертированном графе <tex>s \rightsquigarrow r</tex> и отсутствия <tex>r \rightsquigarrow s</tex>, делаем вывод, что <tex>r</tex> была посещена как потомок <tex>s</tex> в дереве поиска в глубину или <tex>r</tex> уже была обработана поиском в глубину на момент начала поиска из <tex>s</tex>. Но тогда <tex>f[s]</tex> > <tex>f[r]</tex>, что является противоречием. Значит, наше предположение об отсутсвии пути <tex>s \rightsquigarrow r</tex> было не верно. Тогда в исходном графе существуют пути как <tex>s \rightsquigarrow r</tex>, так и <tex>r \rightsquigarrow s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.взаимно достижимы
==Пример реализации==
