147
правок
Изменения
Нет описания правки
==Двупроходный алгоритм==
Найти [[Отношение вершинной двусвязности|компоненты вершинной двусвязности]] неориентированного графа можно с помощью [[Обход_в_глубину,_цвета_вершин |обхода в глубину]].
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
если (<tex>u</tex> родитель)
переходим к следующей итерации
если (<tex>v</tex> не посещена)
dfs(<tex>v, -1, -1</tex>)
|width = "310px" |[[Файл:Vertex_doubleconnection_1.png|right|300px|]]<br><center>'''Компоненты обозначены разным цветом'''</center>
|}
<br clear = "all>
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
<br>
