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

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

struct Graph {
    vector<vector<int>> graph;
    vector<int> visited, depth, upDepth;
    set<int> cutpoints;

    void dfs(int v, int p) {
        visited[v] = 1;
        depth[v] = (p == -1 ? 0 : depth[p] + 1);
        upDepth[v] = depth[v];
        int childrenCount = 0;

        for (int to : graph[v]) {
            if (to == p) {
                continue;
            } else if (!visited[to]) {
                dfs(to, v);
                childrenCount++;
                upDepth[v] = min(upDepth[v], upDepth[to]);
                if (p != -1 && upDepth[to] >= depth[v])
                    cutpoints.insert(v);
            } else {
                upDepth[v] = min(upDepth[v], depth[to]);
            }
        }

        if (p == -1 && childrenCount > 1)
            cutpoints.insert(v);
    }

    Graph(int vertexCount) :
        graph(vertexCount), visited(vertexCount), depth(vertexCount), upDepth(vertexCount) {}

    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    set<int> getCutpoints() {
        for (int v = 0; v < graph.size(); v++)
            if (!visited[v])
                dfs(v, -1);
        return cutpoints;
    }
};

Ссылки

Теория:

• e-maxx.ru — Поиск точек сочленения
• neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска точек сочленения
• neerc.ifmo.ru/wiki — Построение компонент вершинной двусвязности
• algorithmica.org — Мосты и точки сочленения
• Калинин П. Мосты и точки сочленения
• Лахно А. Поиск в глубину и его применение

Демонстрация:

• VisuAlgo — Graph Traversal

Код:

• codelibrary/java/graphs/dfs/Biconnectivity.java
• algos/Graphs/CutpointsSearch.cpp

Задачи:

• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2