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