212
правок
Изменения
→Двупроходный алгоритм
Псевдокод второго прохода:
'''paint(function''' <tex>paint(v, color)</tex>, цвет)''': <tex>colors[v]\leftarrow</tex> цветcolor для всех вершин '''for''' <tex>u</tex>\in V : (u, смежных <tex>v) \in E</tex>: если '''if''' <tex>colors[u]</tex> не покрашена== 0: если '''if''' <tex>ret[u] > enter[v]</tex>: увеличиваем максимальный цветmaxColor++ '''<tex>paint'''</tex>(<tex>u</tex>, максимальный цветmaxColor) иначе: '''paintelse''': <tex>paint</tex>(<tex>u</tex>, цветcolor)
...
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.