171
правка
Изменения
Нет описания правки
Псевдокод первого прохода:
'''обнуляем массив enter текущее время := 0 void dfs(v, родитель):
увеличиваем текущее время
enter(v) := текущее время
return(v) := min(return(v), enter(u))
...
обнуляем массив enter
текущее время := 0
для всех вершин v графа:
если enter(v) = 0:
Псевдокод второго прохода:
'''обнуляем массив colors максимальный цвет := 0 void paint(v, цвет):
colors(v) := цвет
для всех вершин u, смежных v:
paint(u, цвет)
...
обнуляем массив colors
максимальный цвет := 0
для всех вершин v графа:
если colors(v) = 0:
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
== Однопроходный алгоритм ==
Можно также искать компоненты реберной двусвязности путем конкатенации циклов. Воспользуемся тем, что реберная двусвязность является отношением эквивалентности на вершинах графа; тогда, если у двух циклов существует хоть одна общая вершина, все вершины, располагающиеся на этих циклах, принадлежат одной компоненте. Более того, две вершины <tex>u</tex> и <tex>v</tex> лежат в одной компоненте реберной двусвязности тогда и только тогда, когда существует последовательность простых циклов <tex>c_1 c_2 ... c_n</tex>, причем <tex>u \in c_1</tex>, <tex>v \in c_n</tex>, и <tex>c_i</tex> имеет с <tex>c_{i + 1}</tex> хотя бы одну общую вершину для всех <tex>i \in {1 ... n - 1}</tex>. Действительно, если зафиксировать один путь от <tex>u</tex> до <tex>v</tex>, а затем искать точки пересечения второго, не имеющего одинаковых ребер с первым, пути с ним, то получится последовательность циклов, точками сочленения между которыми будут как раз точки пересечения путей. И наоборот, последовательность простых циклов легко превратить в два реберно непересекающихся пути.
Совокупность компонент реберной двусвязности будем хранить как систему непересекающихся множеств вершин.
Псевдокод:
'''int dfs(v, родитель): (возвращает 0, если у v и ее потомков нет обратных ребер, и представителя множества, содержащего цикл с v, в обратном случае)
seen(v) = true
value = 0, result = 0
для всех вершин u, смежных v:
если не seen(u):
value = dfs(u, v)
если value > 0:
color(v) = value
result = value
иначе если u не родитель:
color(v) = color(u)
result = color(v)
return result
...
обнуляем массив seen
нумеруем вершины графа натуральными числами от 1 до мощности множества вершин графа
для всех вершин v графа:
color(v) = номер вершины (номер цвета соответствует номеру вершины-представителя в множестве)
для всех вершин v графа:
если не seen(v):
dfs(v, null)'''
Осталось лишь сопоставить всем вершинам отдельно взятой компоненты единственного представителя.
Псевдокод:
'''int relax(v): (возвращает нового представителя)
если color(v) не равен номеру v:
color(v) = relax(color(v))
return color(v)
...
для всех вершин v графа:
relax(v)
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
== См. также ==
[[Отношение реберной двусвязности]]
