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