Изменения

Первый способ найти искомые компоненты {{- --}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета. Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.

'''Первый проход определяет :''' запустим [[Использование обхода в глубину для поиска мостов|алгоритм для каждой вершины поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> две величины: и <tex>enterup(v)</tex> - время входа поиска в глубину в вершину и [[Использование обхода в глубину для поиска мостов#Функция | ret(v)]].

Определим критерий перехода к '''Второй проход:''' окрашиваем вершины, т.е. если перешли по мосту, то оказались в новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]реберной двусвязности.

Основываясь на этом=== Псевдокод второго прохода ===* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, определим алгоритм окраски вершин графа: перешли по мостучто эквивалентно тому, следовательно началась новая что никакая компонентане окрашена.

Псевдокод второго прохода '''function''' paint(<tex>v</tex>, color): colors[<tex>v</tex>] = color '''for''' <tex>(u, v) \in E</tex>: '''if''' colors[<tex>u</tex>] == 0: '''if''' up[<tex>u</tex>] > tin[<tex>v</tex>]: maxColor++ paint(<tex>u</tex>, maxColor) '''else''': paint(<tex>u</tex>, color)

'''paintfunction''' solve(<tex>v</tex>, цвет): '''for''': <tex>colors(v)\leftarrowin V</tex> цвет: для всех вершин <tex>u</tex>, смежных colors[<tex>v</tex>:] = 0 если '''if''' '''not''' visited[<tex>uv</tex> не покрашена:] если <tex>ret(u) = enter dfs(u)</tex>: увеличиваем максимальный цвет <tex>paint(uv</tex>, максимальный цвет) иначе: <tex>paint(u</tex>, цвет) ... обнуляем массив <tex>colors</tex> максимальный цвет <tex>\leftarrow</tex> maxColor = 0 для всех вершин '''for''' <tex>v\in V</tex> графа: если '''if''' colors[<tex>colors(v)</tex> ] == 0: увеличиваем максимальный цвет maxColor++ paint(<tex>paint(v</tex>, максимальный цветmaxColor)'''

Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * <tex> 2 \cdot O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.

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

=== Псевдокод:===

'''function'''paint(<tex>v</tex>)''': <tex>maxcolor</tex> maxColor++ last = -1 '''while''' (пока вершина стека не вершина last != <tex>v</tex> и стек не пустой'''and''' '''not''' stack.empty() извлекаем вершину стека и красим её colors[stack.top()] = maxColor last = stack.top() stack.pop()

'''dfsfunction'''dfs(<tex> v </tex>) <tex> time \leftarrow = time + 1</tex> <tex> stack.push(<tex>v) </tex>) tin[<tex>enter[v] \leftarrow time</tex>] = time up[<tex>ret[v] \leftarrow time </tex>] = time '''for''' всех <tex>(v, u) \in E</tex> смежных с <tex>v</tex>: '''if''' <tex>(v, u)</tex> - — обратное ребро up[<tex>ret[v</tex>] \leftarrow = min(retup[<tex>v</tex>], entertin[<tex>u])</tex>]) '''if''' вершина '''not''' visited[<tex>u</tex> - белая] '''dfs'''(<tex>u</tex>) up[<tex> ret[v</tex>] \leftarrow = min(retup[<tex>v</tex>], retup[<tex>u]) </tex>]) '''if''' up[<tex>ret[u</tex>] > entertin[<tex>v]</tex> ] paint(<tex>paint(u)</tex> )   Так же после вызова dfs нужно не забыть в конце вызвать ещё раз paint.

== Визуализатор См. также ==* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация построение [Построение компонент реберной двусзяностивершинной двусвязности]] ==Литература==Седжвик Роберт. Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах: Пер. с англ./Роберт Седжвик. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* [[Использование обхода в глубину для поиска мостов]]

== Источники информации ==* ''Седжвик Р.'' Фундаментальные алгоритмы на C++. Часть 5: Алгоритмы на графах. Пер. с англ. — СПб.: ООО «ДиаСофтЮП», 2002. — С. 123-128* ''Кузнецов В.А.Кузнецов, Караваев. А.М.Караваев. '' "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bridges-2001| Визуализация {{---}} Построение компонент реберной двусзяности]