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>
===Лемма===
=== Псевдокод ===
'''dfsfunction'''dfs(<tex> v </tex>): <tex> time \leftarrow = time + 1</tex> <tex>enter[v] \leftarrow = time</tex> <tex>ret[v] \leftarrow = time </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'''(u) <tex> ret[v] \leftarrow \= min(ret[v], ret[u]) </tex> '''if''' <tex>ret[u] > enter[v]</tex> ребро <tex>(v, u)</tex> — мост
==См. также==
