Изменения

Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.

'''function''' <tex>paint</tex>(<tex>v</tex>): maxColor++ '''while''' stack.top() != <tex>v</tex> '''and''' '''not''' stack.empty() colors[stack.top()] <tex>\leftarrow</tex> = maxColor stack.pop()

'''function''' <tex>dfs</tex>(<tex> v </tex>) time<tex> \leftarrow</tex> = time + <tex>1</tex>

entertin[<tex>v</tex>] <tex>\leftarrow</tex> = time retup[<tex>v</tex>] <tex> \leftarrow</tex> = time '''for''' <tex>u \in V : (v, u) \in E</tex>:

retup[<tex>v</tex>] <tex> \leftarrow </tex> = min(retup[<tex>v</tex>], entertin[<tex>u</tex>])

<tex>dfs</tex>(<tex>u</tex>) retup[<tex>v</tex>] <tex>\leftarrow</tex> = min(retup[<tex>v</tex>], retup[<tex>u</tex>]) '''if''' retup[<tex>u</tex>] > entertin[<tex>v</tex>] <tex> paint</tex>(<tex>u</tex>)