Изменения
Нет описания правки
{{Задача|definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|)</tex>}}
== Алгоритм ==
[[Файл:Joint_point_2_rsz.png|280px|thumb|left|<font color=red>Красным </font> цветом обозначены точки сочленения<br><font color=blue>Синим </font> — ребра по которым идет DFS]]
Пусть <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> в дереве поиска.
Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] < \geqslant tin[u]</tex>.
Таким образом, если для текущей вершины <tex>v \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \ge geqslant tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.
<br clear="all">
'''for''' u: (v, u) '''in''' G
'''if''' u == p
'''continue''' '''if''' visited[u] == ''true''
up[v] = min(up[v], tin[u])
'''else'''
dfs(u, v)
up[v] = min(up[v], tin[u])
'''if''' up[to] >= tin[v] '''&& ''' p != -1 <font color=darkgreen>//если граф состоит из 2 вершин и одного ребра, то p != -1 спасёт, иначе выведет 1 точку сочленения </font>
v — cutpoint
'''if''' v — '''is''' root
v — cutpoint
'''for''' i = 1 '''to''' n
'''if''' '''not''' visited[i] == ''false''
dfs(i, -1)
