212
правок
Изменения
→Двупроходный алгоритм
'''Первый проход:
[[Использование обхода в глубину для поиска точек сочленения|Ищем ищем точки сочленения, с помощью обхода в глубину.]] <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>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>paint</tex> для текущей вершины.* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.
'''function''' paint(<tex>v</tex>, color, parent):
'''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>)
'''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)
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
