1632
правки
Изменения
м
rollbackEdits.php mass rollback
* <tex>enter(v)</tex> [[Использование обхода в глубину для топологической сортировки | время входа в вершину <tex>v </tex> ]] <br>
* <tex>enter(x)</tex>, где <tex>x</tex> — потомок <tex>v</tex> <br>
* <tex>enter(xw)</tex>, где <tex>(w, x)</tex> — обратное ребро, а <tex>w</tex> — потомок <tex>v</tex> (в нестрогом смысле) <br>
===Лемма===
=== Псевдокод ===
'''function''' dfs(v):
time = time + 1
enter[v] = time
'''for''' всех u смежных с v
'''if''' (v, u) — обратное ребро
ret[v] = <tex>\min</tex>(ret[v], enter[u])
'''if''' вершина u — белая
dfs(u)
ret[v] = <tex>\min</tex>(ret[v], ret[u])
'''if''' ret[u] > enter[v]
ребро (v, u) — мост
