212
правок
Изменения
→Двупроходный алгоритм
Используем это свойство, чтобы окрасить компоненты вершинной двусвязности в различные цвета.<br>
=== Псевдокод второго прохода ===
* Во время первого запуска <tex>dfs</tex> будут заполняться массивы <tex>tin</tex> и <tex>up</tex>, поэтому при запуске функции <tex>paint</tex> мы считаем, что они уже посчитаны.
* <tex>\mathtt{maxColor}</tex> изначально равен <tex>0</tex>, что эквивалентно тому, что никакое ребро не окрашено.
* <tex>\mathtt{color}</tex> хранит в себе цвет, компоненты, из которой вызвалась функция <tex>\mathttmathrm{paint}</tex> для текущей вершины.
* <tex>\mathtt{parent}</tex> {{---}} это вершина, из которой мы попали в текущую.
'''function''' paint(<tex>v</tex>, color, parent):
'''for''' <tex> u : (v, u) \in E</tex>:
'''if''' <tex>u</tex> == parent
'''continue'''
