Изменения

'''Первый проход:

'''Второй проход:

Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u : returnup[u] \geqslant entertin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>

'''function''' <tex>dfs</tex>(<tex>v</tex>, color, parent): '''for''' <tex> u \in V : (v, u) \in E</tex>: '''if''' <tex>u</tex> == parent '''continue''' '''if''' '''not''' visited[<tex>u</tex>] '''if''' returnup[<tex>u</tex>] <tex>\geqslant</tex> entertin[<tex>v</tex>] newColor <tex>\leftarrow</tex> = maxColor++ col[<tex>vu</tex>] <tex>\leftarrow</tex> = newColor <tex> dfs</tex>(<tex>u</tex>, newColor, <tex>v</tex>) '''else''' col[<tex>vu</tex>] <tex>\leftarrow</tex> = color <tex> dfs</tex>(<tex>u</tex>, color, <tex>v</tex>) '''else''' '''if''' enterup[<tex>u</tex>] <tex>\leqslant</tex> entertin[<tex>v</tex>] col[<tex>vu</tex>] <tex>\leftarrow</tex> = color ... '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>] <tex> dfs</tex>(<tex>v</tex>, -1, -1)

В алгоритме выполняется два прохода <tex>dfs</tex>, каждый из которых работает <tex>O(|V | + |E|)</tex>. Значит время работы алгоритма <tex>O(|V | + |E|)</tex>.