Изменения

Перейти к: навигация, поиск

Построение компонент рёберной двусвязности

305 байт добавлено, 08:21, 27 октября 2011
Нет описания правки
если не seen(v):
dfs(v, null)'''
Осталось лишь сопоставить всем вершинам отдельно взятой компоненты единственного представителя.
Теперь две вершины имеют одинаковый цвет тогда и только тогда, когда они принадлежат одной компоненте реберной двусвязности.
 
Время работы dfs <tex> O(|V| + |E|)</tex>. А время восстановления <tex> O(|V|)</tex>, так как [[Анализ реализации с ранговой эвристикой | снм]].
Итоговое время работы алгоритма <tex> O(|V| + |E|)</tex>.
== См. также ==
152
правки

Навигация