二辺連結成分分解・橋の列挙

計算量

$O(E + V)$

使い方

g は無向グラフ．任意の辺 (u,v) に対して逆辺 (v,u) を持つグラフとして表現する．戻り値の first は cmp[v] = 頂点 v が含まれる二重辺連結成分分解の番号となるような vector<int> cmp を返す．トポロジカル順序の逆に振られる．second は橋となる辺のリスト．

実装

std::pair<std::vector<int>, Edges> bridge(const Graph& g) {
    const int n = g.size();
    int idx = 0, s = 0, t = 0, k = 0;
    std::vector<int> ord(n, -1), onS(n), stk(n), roots(n), cmp(n);
    Edges brdg;
    std::function<void(int, int)> dfs = [&](int v, int u) {
        ord[v] = idx++;
        stk[s++] = v;
        onS[v] = true;
        roots[t++] = v;
        for (auto& e : g[v]) {
            int w = e.dst;
            if (ord[w] == -1)
                dfs(w, v);
            else if (u != w && onS[w])
                while (ord[roots[t - 1]] > ord[w]) --t;
        }
        if (v == roots[t - 1]) {
            brdg.emplace_back(u, v, 0);
            while (1) {
                int w = stk[--s];
                onS[w] = false;
                cmp[w] = k;
                if (v == w) break;
            }
            --t;
            ++k;
        }
    };
    for (int u = 0; u < n; u++) {
        if (ord[u] == -1) {
            dfs(u, n);
            brdg.pop_back();
        }
    }
    return std::make_pair(cmp, brdg);
}

検証

ARC039 D - 旅行会社高橋君 (Submission)

参考文献

Spaghetti Source - 橋，二重辺連結成分分解