Точки сочленения. Компоненты вершинной двусвязности

• Для каждой вершины v будем подсчитывать глубину depth[v] и величину upDepth[v] — минимальную глубину некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
• Вершина v является точкой сочленения, если у неё имеется хотя бы один потомок u, такой что из поддерева этого потомка в дереве обхода в глубину нет обратных рёбер в предков вершины v (upDepth[u] >= depth[v]).
• Корень дерева обхода в глубину (parent == -1) является точкой сочленения тогда и только тогда, когда у него более одного непосредственного потомка.

vector<int> g[V_CNT];
bool u[V_CNT];
int depth[V_CNT], upDepth[V_CNT]; 

void dfs(int v, int parent = -1) {
    u[v] = 1;
    depth[v] = upDepth[v] = (parent == -1 ? 0 : depth[parent] + 1);
    int childrenCount = 0;
    for (int i = 0; i < g[v].size(); i++) {
        if (!u[g[v][i]]) {
            dfs(g[v][i], v);
            childrenCount++;
            upDepth[v] = min(upDepth[v], upDepth[g[v][i]]);
            if (parent != -1 && upDepth[g[v][i]] >= depth[v])
               /* v - точка сочленения */;
        } else if (g[v][i] != parent)
            upDepth[v] = min(upDepth[v], depth[g[v][i]]);
    }
    if (parent == -1 && childrenCount > 1)
       /* v - точка сочленения */;
}

for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs(i);

Ссылки

• e-maxx.ru — Поиск точек сочленения
• neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска точек сочленения
• neerc.ifmo.ru/wiki — Построение компонент вершинной двусвязности
• algorithmica.org — Мосты и точки сочленения
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
• Калинин П. Поиск в глубину
• Лахно А. Поиск в глубину и его применение
• VisuAlgo — Graph Traversal
• CodeLibrary — Biconnected components, bridges and cut points
• Algos — Algorithm for finding all cutpoints in the graph