212
правок
Изменения
→Двупроходный алгоритм
Воспользуемся ранее доказанной [[Использование обхода в глубину для поиска мостов#Лемма | леммой]]. Получается {{---}} перешли по мосту, следовательно началась новая компонента.
'''Первый проход:''' Ищем запустим [[Использование обхода в графе мостыглубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>.
'''Второй проход:''' Окрашиваем окрашиваем вершины, т.е.Первым проходом запустим [[Использование обхода если перешли по мосту, то оказались в глубину для поиска мостов|алгоритм для поиска мостов]], чтобы посчитать две величины: <tex>tin(v)</tex> и <tex>up(v)</tex>новой компоненте реберной двусвязности.
=== Псевдокод второго прохода ===
* В переменной <tex>\mathtt{color}</tex> хранится цвет текущей компоненты.
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакая компонента не окрашена.
'''function''' paint(<tex>v</tex>, color):
