148
правок
Изменения
Нет описания правки
Таким образом, если для текущей вершины <tex>v \ne root \, \exists</tex> непосредственный сын <tex>v</tex>: <tex>up[v] \ge tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения; в противном случае она точкой сочленения не является.
= Реализация =
<tex>time \leftarrow 0</tex>
dfs(<tex>root</tex>, -1);
<br>Время работы алгоритма совпадает с временем работы <tex> dfs </tex>. Он равен <tex> O(V + E) </tex>
= Источники =
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
