Изменения
исправлены мелкие ошибки
}
[[Точка сочленения, эквивалентные определения|Точка сочленения]] принадлежит как минимум двум компонентам вершинной двусвязаностидвусвязности.Вершина <tex> u \ne root </tex> является точкой сочленения, если у нее <tex> \exists </tex> непосредственный сын <tex> v : return[v]\ge enter[u] </tex>. <br> Это так же значит, что ребро <tex> uv </tex> содержится в другой компоненте вершинной двусвязности, нежели ребро, по которому мы пришли в вершину <tex> v </tex> , используя поиск в глубину. <br>
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
'''Псевдокод второго прохода:
}
void start() {
used для всех вершин заполняем false;
для всех v вершин графа:
если (!used[v]):
dfs(v, max(c)-1, -1);
}
Ребра каждой из компонент вершинной двусвязности окажутся окрашенными в свой цвет.
==Однопроходный алгоритм==
Предположим, что граф содержит точку сочленения <tex> i' \in V </tex> , за которой следует один или несколько блоков, содержащих вершины <tex> V' \subset V </tex>. В таком случае: <br>
При этом в <tex> G </tex> не может быть обратных дуг из <tex> V' </tex> в <tex> V \setminus V' </tex>. Воспользуемся этим.
Заведем стек, в который будем записывать все дуги в порядке их обработки. Если обнаружена точка сочленения, дуги очередного блока окажутся в этом стеке, начиная с дуги дерева обхода, которая привела в этот блок, до верхушки стека.
переходим к следующей итерации
если (!used[u]):
stack <- .push(vu);
dfs(u, v);
если (return[u] >= enter[v]):
если (return[u] < return[v]):
return[v] = return[u];
== См. также ==
*[[Использование обхода в глубину для поиска точек сочленения]]*[[Построение компонент реберной двусвязности]]
==Литература==
* В.А.Кузнецов, А.М.Караваев. "Оптимизация на графах" - Петрозаводск, Издательство ПетрГУ 2007
