Изменения
→Доказательство корректности алгоритма
<tex>\Leftarrow</tex>
1) Рассмотрим корень <tex>r</tex> дерева второго обхода в глубину, в котором оказались вершины Вершины <tex>s</tex> и <tex>t</tex>оказались в одной компоненте связности, т.е. принадлежат одному и тому же дереву поиска в глубину на третьем этапе алгоритма. Это значитЗначит, что в графе <tex>G</tex> существует путь они обе достижимы из корня <tex>r</tex> в <tex>s</tex> и в <tex>t</tex>этого дерева.
2) Вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Из этого мы получаем 2 случая:
