1
правка
Изменения
Исправление критичного бага
'''Первый проход:
[[Использование обхода в глубину для поиска точек сочленения|Ищем ищем точки сочленения.с помощью обхода в глубину]] , заполняем массивы <tex>tin</tex> и <tex>up</tex>. <br>
'''Второй проход:
[[Точка сочленения, эквивалентные определения|Точка точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
Вершина <tex> v \ne root </tex> является точкой сочленения, если у нее есть сын <tex> u</tex>, такой что <tex> up[u] \geqslant tin[v] </tex>. <br> Это также значит, что ребро <tex> vu </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. Получается, что перейдя по этому ребру, мы окажемся в другой компоненте вершинной двусвязности. <br>
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
=== Псевдокод второго прохода ===
* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathrm{paint}</tex> для текущей вершины.* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.
'''function''' paint(<tex>v</tex>, color, parent):
visited[<tex>v</tex>] = '''true''' '''for''' <tex> u : (v, u) \in E</tex>:
'''if''' <tex>u</tex> == parent
'''continue'''
'''if''' '''not''' visited[<tex>u</tex>]
'''if''' up[<tex>u</tex>] <tex>\geqslant</tex> tin[<tex>v</tex>]
newColor = maxColor++maxColor
col[<tex>vu</tex>] = newColor
paint(<tex>u</tex>, newColor, <tex>v</tex>)
col[<tex>vu</tex>] = color
paint(<tex>u</tex>, color, <tex>v</tex>)
'''else''' '''if''' uptin[<tex>u</tex>] <tex>\leqslant<</tex> tin[<tex>v</tex>]
col[<tex>vu</tex>] = color
'''function''' solve():
'''for''' <tex> v \in V</tex>:
'''for''' <tex> v \in V</tex>:
'''if''' '''not''' visited[<tex>v</tex>]
maxColor++ paint(<tex>v</tex>, -1maxColor, -1)
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
=== Псевдокод ===
'''function''' paint(<tex>v</tex>, parent):
visited[<tex>v</tex>] = '''true'''
tin[<tex>v</tex>] = up[<tex>v</tex>] = time++
'''for''' <tex> (v, u) \in E</tex>:
'''else''' '''if''' tin[<tex>u</tex>] < tin[<tex>v</tex>]
stack.push(<tex>vu</tex>)
'''if''' tin[<tex>u</tex>] < up[<tex>v</tex>]
up[<tex>v</tex>] = tin[<tex>u</tex>]
'''else''' '''if''' up[<tex>v</tex>] > tin[<tex>u</tex>]
up[<tex>v</tex>] = up[<tex>u</tex>]
'''function''' solve():
'''for''' <tex> v \in V</tex>:
'''for''' <tex> v \in V</tex>:
'''if''' '''not''' visited[<tex>v</tex>]: time = 0 maxColor++ paint(<tex>v</tex>, -1)<br>
Во время алгоритма совершается один проход <tex>dfs</tex>, который работает за <tex>O(|V| + |E|)</tex>. Внутри него совершается еще цикл, который суммарно выполняет <tex>O(|E|)</tex> операций, т.к. каждое ребро может быть добавлено в стек только один раз. Следовательно, общее время работы алгоритма <tex>O(|V| + |E|) + O(|E|) = O(|V| + |E|)</tex>
== См. также ==
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент реберной двусвязности]]
