152
правки
Изменения
→Двупроходный алгоритм
Первый способ найти искомые компоненты - сначала определить критерий перехода в новую компоненту реберной двусвязности, а затем покрасить вершины графа в нужные цвета.
Первый проход определяет для каждой вершины <tex>v</tex> две величины: <tex>enter(v)</tex> - время входа поиска в глубину в вершину, <tex>return(v)</tex> - минимальное из времен входа вершин, достижимых из <tex>v</tex> по [[Обход Использование обхода в глубину, цвета вершиндля поиска мостов#Функция |дереву <tex>dfs</tex>]] и не более, чем одному обратному ребру. <tex>returnret(v)</tex> находится как <tex>min(enter(v), return(u), enter(w))</tex> для всех <tex>u</tex> - сыновей <tex>v</tex> в дереве <tex>dfs</tex>, <tex>w</tex> - соседей <tex>v</tex> по обратным ребрам. Важно, что ребро к родителю дерева <tex>dfs</tex> не является обратным ребром обхода.]]
Определим критерий перехода к новой компоненте.
для всех вершин u, смежных v:
если colors(u) равен нулю (вершина не покрашена):
если returnret(u) = enter(u):
увеличиваем максимальный цвет
paint(u, максимальный цвет)
