322
правки
Изменения
→Двупроходный алгоритм
== Двупроходный алгоритм ==
Первый способ найти искомые компоненты {{- --}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета.
Первым проходом запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>enter(v)</tex> и <tex>ret(v)</tex>.
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
Время работы алгоритма будет время работы двух запусков dfs, то есть 2 * <tex> 2 \cdot O(|V| + |E|)</tex>, что есть <tex> O(|V| + |E|)</tex>.
== Однопроходный алгоритм ==
