Изменения

Пусть <tex>T</tex> - — дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> - — корень <tex>T</tex>. Вершина <tex>u \ne root</tex> - — точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> - — сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>. <tex>root</tex> - — точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.

#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что не существует пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> - — предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> - — предпоследняя вершина на этом пути, <tex>w</tex> - — потомок <tex>v</tex>. <tex>(w, x)</tex> - — не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> - — обратное ребро, что противоречит условию.#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> - — точка сочленения.

#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> - — связный <tex>\Rightarrow u</tex> - — не точка сочленения.#Пусть <tex>root</tex> - — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен - — противоречие с тем, что <tex>root</tex> - — точка сочленения.

Пусть <tex>tin[u]</tex> - — время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.

if (<tex>v</tex> посещено) //<tex>v - </tex> — предок вершины <tex>u</tex>, <tex>uv - </tex> — обратное ребро

else //<tex>v - </tex> — ребенок вершины <tex>u</tex>

Время работы алгоритма совпадает с [[Обход в глубину, цвета вершин#Время работы|временем работы ]] <tex> dfs </tex>, а именно <tex> O(V + E) </tex>.