Изменения

Перейти к: навигация, поиск
Двупроходный алгоритм
Псевдокод второго прохода:
'''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)
...
обнуляем массив '''for''' <tex>v \in V</tex> : <tex>colors[v] \leftarrow 0 </tex> максимальный цвет maxColor <tex>\leftarrow 0</tex> для всех вершин '''for''' <tex>v\in V</tex> графа: если '''if''' <tex>colors[v] == 0</tex>: увеличиваем максимальный цветmaxColor++ '''<tex>paint'''</tex>(<tex>v</tex>, максимальный цветmaxColor)
Вершины каждой из компонент реберной двусвязности окажутся окрашенными в свой цвет.
212
правок

Навигация