212
правок
Изменения
→Двупроходный алгоритм
'''Первый проход:
'''Второй проход:
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязности.
Вершина <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>maxColor</tex> изначально равен 0, что эквивалентно тому, что ребро не окрашено.* <tex>color</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>paint</tex> для текущей вершины.* <tex>parent</tex> {{---}} это вершина, из которой мы попали в текущую. '''function''' <tex>dfs</tex>paint(<tex>v</tex>, color, parent):
'''for''' <tex> u : (v, u) \in E</tex>:
'''if''' <tex>u</tex> == parent
newColor = maxColor++
col[<tex>vu</tex>] = newColor
'''else'''
col[<tex>vu</tex>] = color
'''else''' '''if''' up[<tex>u</tex>] <tex>\leqslant</tex> tin[<tex>v</tex>]
col[<tex>vu</tex>] = color
'''function''' solve(): '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>] dfs(<tex>v,</tex>) '''for''' <tex> v \in V</tex>: visited[<tex>v</tex>] = '''false''' '''for''' <tex> v \in V</tex>: '''if''' '''not''' visited[<tex>v</tex>] dfs paint(<tex>v</tex>, -1, -1)
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
