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

Задача

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

Алгоритм

Запустим обход в глубину из произвольной вершины [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] является точкой сочленения; в противном случае она точкой сочленения не является.

Реализация

bool used[];
int tin[];
int up[];
bool answer[];                              //для каждой вершины содержится булево значение - является она точкой сочленения или нет. изначально все значения false
int time;

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

int main()
{
    ...                                     //инициализация графа, выбор корня дерева обхода root
    time = 0;
    dfs(root, -1);
    return 0;
}

Для поиска точек сочленения в несвязном графе, необходимо модифицировать функцию main следующим образом:

int main()
{
    ...
    for (root из V)
        if (!used[root])
        {
            time = 0;
            dfs(root, -1);
        }
    return 0;
}

Источники

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.