1632
правки
Изменения
м
'''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>:
retup[<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.
rollbackEdits.php mass rollback
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.
'''Первый проход:''' Ищем запустим [[Использование обхода в графе мостыглубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>.
'''Второй проход:''' Окрашиваем окрашиваем вершины, т.е.Первым проходом запустим [[Использование обхода если перешли по мосту, то оказались в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>новой компоненте реберной двусвязности.
=== Псевдокод второго прохода ===
* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакая компонента не окрашена.
'''function''' paint(<tex>v</tex>, color):
Однопроходный алгоритм строится на базе алгоритма поиска мостов. Во-первых, создадим глобальный [[Стек|стек]], и при спуске по дереву <tex> dfs </tex> добавляем в него вершины. Во-вторых, когда возвращаемся назад, проверяем не является ли ребро мостом (при помощи [[Использование обхода в глубину для поиска мостов#Лемма | леммы]]). Если это так, то то все вершины, находящиеся до текущего потомка в стеке, принадлежат одной компоненте.Заметим, что эта компонента будет висячей вершиной в дереве блоков и мостов, так как обходили граф поиском в глубину. Значит, ее можно выкинуть и продолжить поиск в оставшемся графе. Действуя по аналогии в получившемся графе, найдем оставшиеся компоненты реберной двусвязности.
=== Псевдокод ===
stack.push(<tex>v</tex>)
'''if''' <tex>(v, u)</tex> — обратное ребро
'''if''' '''not''' visited[<tex>u</tex>]
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
Время работы dfs <tex> O(|V| + |E|)</tex>. Покраска за <tex> O(|V|) </tex>.
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
== См. также ==
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
== Источники информации ==
