Изменения

Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то они будут взаимно достижимы и в графе <tex>H</tex>. Рассмотрим дерево обхода в глубину графа <tex>H</tex>. Поскольку вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы, то очевидно, что одна из них окажется в поддереве другой. Без потери общности скажем, что вершина <tex>t</tex> оказалась в поддереве вершины <tex>s</tex>. Значит, время выхода из вершины <tex>t</tex> будет меньше, чем время выхода из вершины <tex>s</tex>. Соответственно, во время третьего шага алгоритма вершина <tex>s</tex> будет рассмотрена раньше, чем вершина <tex>t</tex>, а значит, вершина <tex>st</tex> снова попадет в ее поддерево, и они окажутся в одной компоненте сильной связности.