Изменения

Алгоритм, если Рекурсивый алгоритм на основе обхода в глубину.Если мы посетили вершину, то добавляем её в стек. Так же как раньше <tex>ret[v]</tex> и <tex>enter[v]</tex>. Теперь определим, когда надо окрасить компоненту.Если мы возвращаясь (в рекурсии) обратно оказались в вершине, которая является вершиной моста, то все вершины, находящиеся, до текущей в стеке, принадлежат этой компоненте. Это следует из того, что [[Граф компонент реберной двусвязности | граф блоков и мостов, является деревом]]. По свойству обхода в ширинуглубину, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её можно выкинут и рассматривать оставшийся граф. Действуя по аналогии мы всегда выкидываем компоненту реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте, либо если моста нет, то окрашиваемся всё, что лежит в стеке.

maxcolor++;

извлекаем вершину стека и красим её;

state[v] = 1; ret[v] = enter[v] = ++time;

ret[v] = min(ret[v], enter[u]);

dfs(u, v); ret[v] = min(ret[v], ret[u]);

paint(u); state[v] = 2;

== См. также Визуализатор ==* [[Обход в глубину, цвета вершин|Oбхода в глубину]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент вершинной двусвязности]]* [[Использование обхода в глубину для поиска мостов]]