ホーム > libalgo

二点連結成分分解・関節点の列挙

計算量

$O(E + V)$

使い方

g
無向グラフ.任意の辺 (u,v) に対して逆辺 (v,u) を持つグラフとして表現する.
art (戻り値)
関節点のリストが入る.ある関節点 u が k 個の二重連結成分をつないでいる場合,(k-1) 個の u が入る.嫌なら sort, unique, erase する. UnionFind 木を使って,両側とも art に含まれない辺の両側を union していくと,二重連結成分分解ができる.

実装

std::vector<int> articulationPoint(const Graph& g) {
    int n = g.size(), idx;
    std::vector<int> low(n), ord(n), art;
    std::function<void(int)> dfs = [&](int v) {
        low[v] = ord[v] = ++idx;
        for (auto& e : g[v]) {
            int w = e.dst;
            if (ord[w] == 0) {
                dfs(w);
                low[v] = std::min(low[v], low[w]);
                if ((ord[v] == 1 && ord[w] != 2) || (ord[v] != 1 && low[w] >= ord[v]))
                    art.push_back(v);
            } else
                low[v] = std::min(low[v], ord[w]);
        }
    };
    for (int u = 0; u < n; u++)
        if (ord[u] == 0) {
            idx = 0;
            dfs(u);
        }
    // sort(art.begin(), art.end());
    // art.erase(unique(art.begin(), art.end()), art.end());
    return art;
}

検証

AOJ GRL3A (Submission)

参考文献

Spaghetti Source - 関節点,二重頂点連結成分分解