212
правок
Изменения
→Однопроходный алгоритм
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный стек, и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
=== Псевдокод:===
'''function''' <tex>paint</tex>(<tex>v</tex>)''': <tex>maxcolor</tex>maxColor++ '''while''' stack.top(пока вершина стека не вершина ) != <tex>v</tex> и стек не пустой'''and''' '''not''' stack.empty() извлекаем вершину стека и красим её colors[stack.top()] <tex>\leftarrow</tex> maxColor stack.pop()
'''dfsfunction'''<tex>dfs</tex>(<tex> v </tex>) time<tex> time \leftarrow </tex> time + <tex>1</tex> <tex> stack.push(<tex>v) </tex>) enter[<tex>enter[v</tex>] <tex>\leftarrow time</tex>time ret[<tex>ret[v</tex>] <tex> \leftarrow time </tex>time '''for''' всех <tex>u</tex> смежных с <tex>\in V : (v, u) \in E</tex>: '''if''' <tex>(v, u)</tex> — обратное ребро ret[<tex>ret[v</tex>] <tex> \leftarrow </tex> min(ret[<tex>v</tex>], enter[<tex>u])</tex>]) '''if''' вершина '''not''' visited[<tex>u</tex> — белая] '''<tex>dfs'''</tex>(<tex>u</tex>) ret[<tex> ret[v</tex>] <tex>\leftarrow </tex> min(ret[<tex>v</tex>], ret[<tex>u]) </tex>]) '''if''' ret[<tex>ret[u</tex>] > enter[<tex>v]</tex> ] '''<tex>paint'''</tex>(<tex>u</tex>)
