Изменения

Перейти к: навигация, поиск

Использование обхода в глубину для поиска точек сочленения

Нет изменений в размере, 08:28, 11 декабря 2011
Алгоритм
Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < tin[u]</tex>.
Таким образом, если для текущей вершины <tex>v \ne root \, \exists</tex> непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения; , в противном случае она точкой сочленения не является.
= Реализация =
Анонимный участник

Навигация