Изменения

Первым проходом запустим Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма |алгоритм для поиска мостовлеммой]]. Получается {{---}} перешли по мосту, чтобы посчитать две величины: <tex>enter(v)</tex> и <tex>ret(v)</tex>следовательно началась новая компонента.

Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной '''Первый проход:''' запустим [[Использование обхода в глубину для поиска мостов#Лемма | леммойалгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>.

Основываясь на этом'''Второй проход:''' окрашиваем вершины, определим алгоритм окраски вершин графа: т.е. если перешли по мосту, следовательно началась новая компонентато оказались в новой компоненте реберной двусвязности.

'''function''' <tex>paint</tex>(<tex>v</tex>, color): colors[<tex>v</tex>] <tex>\leftarrow</tex> = color '''for''' <tex>u \in V : (u, v) \in E</tex>: '''if''' colors[<tex>u</tex>] == 0: '''if''' retup[<tex>u</tex>] > entertin[<tex>v</tex>]: maxColor++ <tex> paint</tex>(<tex>u</tex>, maxColor) '''else''': <tex> paint</tex>(<tex>u</tex>, color) ... '''function''' solve(): '''for''' <tex>v \in V</tex> : colors[<tex>v</tex>] = 0 '''if''' '''not''' visited[<tex>\leftarrowv</tex> 0] maxColor dfs(<tex>\leftarrowv</tex> ) maxColor = 0 '''for''' <tex>v \in V</tex> : '''if''' colors[<tex>v</tex>] == 0: maxColor++ <tex> paint</tex>(<tex>v</tex>, maxColor)

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

'''function''' <tex>paint</tex>(<tex>v</tex>): maxColor++ last = -1 '''while''' stack.top() last != <tex>v</tex> '''and''' '''not''' stack.empty() colors[stack.top()] <tex>\leftarrow</tex> = maxColor last = stack.top() stack.pop()

'''function''' <tex>dfs</tex>(<tex> v </tex>) time<tex> \leftarrow</tex> = time + <tex>1</tex>

entertin[<tex>v</tex>] <tex>\leftarrow</tex> = time retup[<tex>v</tex>] <tex> \leftarrow</tex> = time '''for''' <tex>u \in V : (v, u) \in E</tex>:

ret up[<tex>v</tex>] <tex> \leftarrow </tex> = min(retup[<tex>v</tex>], entertin[<tex>u</tex>])

<tex>dfs</tex>(<tex>u</tex>) retup[<tex>v</tex>] <tex>\leftarrow</tex> = min(retup[<tex>v</tex>], retup[<tex>u</tex>]) '''if''' retup[<tex>u</tex>] > entertin[<tex>v</tex>] <tex> paint</tex>(<tex>u</tex>) Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.

* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация построение {{---}} Построение компонент реберной двусзяности]