二重頂点連結成分分解

二重頂点連結成分分解の実装です。

追記：誤りがあったので大幅に変更しました。

名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。

任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節点」を含まないような構造(二重頂点連結成分)に分解します。

二重頂点連結成分のことをあえて「構造」と書いたのは、頂点が必ず一つの成分に含まれるとは限らないからです。一方各辺は必ず一つの連結成分に属するので、すべての辺集合を、二重頂点連結成分をなす辺集合に分割すると考えることができます。

以下のグラフを二重頂点連結成分分解することを考えてみます。

まず関節点を列挙して、その点の周りでグラフを切ります。

連結成分に注意して、切れ目を適切に繋ぎます。

このギザギザで囲まれた部分が二重頂点連結成分になります。

番号5に含まれる辺集合に間違いがありました。その集合は二つの別の集合に分かれます。

実装は少しややこしいですが、$LowLink$ におけるordとlowを適切に見ながら、閉路ごとに辺集合をまとめていけばよいです。

bcに辺集合のvectorが入ります。tmpにはこれまでに見た辺を一旦格納しています。

struct BiconnectedComponent {
        vector<int> ord, low;
        vector<bool> used;
        vector<vector<int>> g;
        vector<vector<pair<int, int>>> bc;
        vector<pair<int, int>> tmp;
        int n, k = 0;
        BiconnectedComponent(const vector<vector<int>> &g) : g(g) {
                n = g.size();
                ord.resize(n, -1);
                low.resize(n, -1);
                used.resize(n, false);
        }
        void dfs(int u, int prev) {
                used[u] = true;
                ord[u] = k ++;
                low[u] = ord[u];
                int cnt = 0;
                for (auto v : g[u]) if (v != prev) {
                        if (ord[v] < ord[u]) { 
                                tmp.emplace_back(min(u, v), max(u, v));
                        }
                        if (!used[v]) {
                                cnt ++;
                                dfs(v, u);
                                low[u] = min(low[u], low[v]);
                                if (low[v] >= ord[u]) {
                                        bc.push_back({});
                                        while (true) {
                                                pair<int, int> e = tmp.back();
                                                bc.back().emplace_back(e);
                                                tmp.pop_back();
                                                if (min(u, v) == e.first && max(u, v) == e.second) {
                                                        break;
                                                }
                                        }
                                }
                        } else {
                                low[u] = min(low[u], ord[v]);
                        }
                }
        }
};

以下の問題で使えます（この問題では上の実装のような高速なやり方ではなくてもできます）。

https://beta.atcoder.jp/contests/arc062/tasks/arc062_d

以上です。

参考
https://en.wikipedia.org/wiki/Biconnected_component
http://www.prefield.com/algorithm/graph/articulation_point.html