Первый способ найти искомые компоненты {{---}} сначала определить критерий перехода в новую [[Отношение реберной двусвязности#Компоненты реберной двусвязности|компоненту реберной двусвязности]], а затем покрасить вершины графа в нужные цвета.
Первым проходом запустим Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма |алгоритм для поиска мостовлеммой]]. Получается {{---}} перешли по мосту, чтобы посчитать две величины: <tex>enter(v)</tex> и <tex>ret(v)</tex>следовательно началась новая компонента.
Определим критерий перехода к новой компоненте.Воспользуемся ранее доказанной [[Использование обхода '''Первый проход:''' Ищем в глубину для поиска мостов#Лемма | леммой]]графе мосты.
Основываясь на этом'''Второй проход:''' Окрашиваем вершины.Первым проходом запустим [[Использование обхода в глубину для поиска мостов|алгоритм для поиска мостов]], определим алгоритм окраски вершин графачтобы посчитать две величины: перешли по мосту, следовательно началась новая компонента<tex>tin(v)</tex> и <tex>up(v)</tex>.
=== Псевдокод второго прохода ===
'''function''' <tex>paint</tex>(<tex>v</tex>, color): colors[<tex>v</tex>] <tex>\leftarrow</tex> = color '''for''' <tex>u \in V : (u, v) \in E</tex>: '''if''' colors[<tex>u</tex>] == 0: '''if''' retup[<tex>u</tex>] > entertin[<tex>v</tex>]: maxColor++ <tex> paint</tex>(<tex>u</tex>, maxColor) '''else''': <tex> paint</tex>(<tex>u</tex>, color) ... '''function''' solve(): '''for''' <tex>v \in V</tex> : colors[<tex>v</tex>] = 0 '''if''' '''not''' visited[<tex>\leftarrowv</tex> 0] maxColor dfs(<tex>\leftarrowv</tex> ) maxColor = 0 '''for''' <tex>v \in V</tex> : '''if''' colors[<tex>v</tex>] == 0: maxColor++ <tex> paint</tex>(<tex>v</tex>, maxColor)
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
