Изменения

Построение компонент рёберной двусвязности

21 байт добавлено, 06:43, 24 ноября 2011

→‎Однопроходный алгоритм

'''paint(<tex>v</tex>)''':

<tex>maxcolor</tex>++

'''while''' (пока вершина стека не вершина <tex>v</tex> и стек не пустой) извлекаем вершину стека и красим её

'''for''' всех <tex>u</tex> смежных с <tex>v</tex>

''if'' <tex>(v, u)</tex> - обратное ребро

<tex>ret[v] \leftarrow min(ret[v], enter[u])</tex>

'''if''' вершина <tex>u</tex> - белая

'''dfs'''(<tex>u</tex>)

<tex> ret[v] \leftarrow min(ret[v], ret[u]) </tex>

'''if''' <tex>ret[u] > enter[v]</tex>

'''paint'''(<tex>~~paint(~~u)</tex> )

Анонимный участник