Изменения
→Двупроходный алгоритм
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]].
Основываясь на этом, определим алгоритм окраски вершин графа. Перешли : перешли по мосту, следовательно началась новая компонента.
Псевдокод второго прохода:
'''void paint(<tex>v</tex>, цвет)''': <tex>colors(v) := \leftarrow</tex> цвет для всех вершин <tex>u</tex>, смежных <tex>v</tex>: если colors(<tex>u) равен нулю (вершина </tex> не покрашена): если <tex>ret(u) = enter(u)</tex>:
увеличиваем максимальный цвет
<tex>paint(u</tex>, максимальный цвет)
иначе:
<tex>paint(u</tex>, цвет)
...
обнуляем массив <tex>colors</tex> максимальный цвет := <tex>\leftarrow</tex> 0 для всех вершин <tex>v </tex> графа: если <tex>colors(v) </tex> = 0:
увеличиваем максимальный цвет
<tex>paint(v</tex>, максимальный цвет)'''
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
