Изменения

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

'''void paint(int <tex>v</tex>)''': <tex>maxcolor</tex>++ '''while ''' (пока вершина стека не вершина <tex>v</tex> и стек не пустой)