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

Задача

Дан связный неориентированный граф. Требуется найти все точки сочленения в нем.

Алгоритм

Запустим обход в глубину из произвольной вершины [math]root[/math] графа [math]G(V, E)[/math]. Рассмотрим [math]u \in V[/math]:

1. [math]u \ne root[/math]. Тогда, если найдётся такой потомок [math]v[/math] вершины [math]u[/math] в дереве поиска, что ни из него, ни из какого-либо его потомка нет ребра в предка вершины [math]u[/math], то вершина [math]u[/math] будет являться точкой сочленения. В противном случае, вершина [math]u[/math] не является точкой сочленения.
2. [math]u = root[/math]. [math]u[/math] - точка сочленения [math]\Leftrightarrow u[/math] имеет хотя бы двух сыновей в дереве поиска в глубину.

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

Тогда, из вершины [math]u[/math] или её потомка есть обратное ребро в её предка [math]\Leftrightarrow \exists[/math] такой сын [math]v[/math], что [math]up[v] \lt tin[u][/math].

Таким образом, если для текущей вершины [math]v \ne root \, \exists[/math] непосредственный сын [math]v[/math]: [math]up[v] \ge tin[u][/math], то вершина [math]u[/math] является точкой сочленения; в противном случае она точкой сочленения не является.

Реализация

В массиве [math]answer[][/math] для каждой вершины содержится булево значение - является она точкой сочленения или нет. Изначально все значения false.

dfs[math](u, \, prev)[/math]
    [math]used[u] \leftarrow[/math]true
    [math]tin[u] \leftarrow time[/math]                          //задание времени входа в вершину u
    [math]up[u] \leftarrow time[/math]                          //задание начального значения up для вершины u
    [math]time \leftarrow time + 1[/math]
    [math]count \leftarrow 0[/math]                              //счетчик количества детей вершины u в дереве обхода
    for [math](v : uv \in E)[/math]
        if [math]v = prev[/math]
            continue
        if [math]used[v][/math]                            //v - предок вершины u, uv - обратное ребро
            [math]up[u] \leftarrow min(up[u], \, tin[v])[/math]
        else                                   //v - ребенок вершины u
            [math]count \leftarrow count + 1[/math]
            dfs[math](v, u)[/math]
            [math]up[u] \leftarrow min(up[u], \, up[v])[/math]
            if [math]up[v] \ge tin[u][/math]
                [math]answer[u] \leftarrow[/math]true           //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения
    if [math]p = -1[/math]                               //является ли u корнем дерева обхода
        [math]answer[u] \leftarrow (count \gt  1)[/math];       //проверка количества детей у корня дерева

Источники

MAXimal::algo