== Однопроходный алгоритм ==
Можно найти компоненты реберной двусвязности за один проход, используя стек. Рекурсивый Однопроходный алгоритм строится на основе обхода в глубинубазе алгоритма поиска мостов.Если мы посетили вершинуВо-первых, создадим глобальный стек, то и при спуске по дереву dfs добавляем её в стекнего вершины. Теперь определимВо-вторых, когда надо окрасить компоненту.Если мы возвращаясь возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в рекурсииглубину для поиска мостов#Лемма | леммы]]) обратно оказались в вершине, которая является вершиной моста. Если это так, то то все вершины, находящиеся, до текущей текущего сына в стеке, принадлежат этой одной компоненте. Это следует из того, что [[Граф компонент реберной двусвязности | граф эта компонента будет висячей вершиной в дереве блоков и мостов, является деревом]]. По свойству обхода так как обходили граф поиском в глубину. Значит, мы окажемся в висячей вершине, покрасим её, то есть эту компоненту покрасим. Её ее можно выкинут выкинуть и рассматривать оставшийся графпродолжить поиск в оставшемся графе. Действуя по аналогии мы всегда выкидываем компоненту в оставшемся графе, найдем оставшиеся компоненты реберной двусвязности следовательно, если мы вернулись в вершину, которая была концом нашего моста, то все вершины лежащие до нашей в стеке, принадлежат данной компоненте, либо если моста нет, то окрашиваемся всё, что лежит в стеке.
Псевдокод:
'''void dfs'''(вершина <tex> v, предок вершины p</tex>): добавляем вершину в в стек; <tex> time \leftarrow time + 1</tex> state <tex> stack.push(v) </tex> <tex>enter[v] = 1\leftarrow time</tex> <tex>ret[v] = enter[v] = ++\leftarrow time</tex> для '''for''' всех вершин <tex>u </tex> смежных с <tex>v:</tex> если ''if'' <tex>(v, u == parent): </tex> - обратное ребро переходим к следующей итерации если (state[u] = 1): <tex>ret[v] = \leftarrow min(ret[v], enter[u])</tex> иначе: если (state[ '''if''' вершина <tex>u] = 0):</tex> - белая '''dfs'''(u, v) <tex> ret[v] = \leftarrow min(ret[v], ret[u])</tex> если ( '''if''' <tex>ret[u] > enter[v] < ret[u]): /tex> <tex>paint(u) state[v] = 2</tex>
