二重辺連結成分分解

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

二重頂点連結成分分解についてはこちらの記事をご覧ください。

無向グラフ上で、橋が存在しない部分グラフを一つの頂点につぶすと、橋を辺とする木ができます。以下は、それをそのまま実装しています。

struct LowLink {
        set<pair<int, int>> bridge;
        vector<int> articulation, ord, low;
        vector<bool> used;
        vector<vector<int>> g;
        int n, k = 0;
        LowLink(const vector<vector<int>> &g) : g(g) {
                n = g.size();
                ord.resize(n, 0);
                low.resize(n, 0);
                used.resize(n, false);
        }
        void dfs(int u, int prev) {
                used[u] = true;
                ord[u] = k ++;
                low[u] = ord[u];
                bool is_articulation = false;
                int cnt = 0;
                for (auto v : g[u]) if (v != prev) {
                        if (!used[v]) {
                                cnt ++;
                                dfs(v, u);
                                low[u] = min(low[u], low[v]);
                                if (low[v] > ord[u]) {
                                        bridge.emplace(min(u, v), max(u, v));
                                } 
                                if (prev != -1 && low[v] >= ord[u]) {
                                        is_articulation = true;
                                }
                        } else {
                                low[u] = min(low[u], ord[v]);
                        }
                }
                if (prev == -1 && cnt > 1) is_articulation = true;
                if (is_articulation) articulation.push_back(u);
        }
};
struct TwoEdgeConnectedComponent {
        int n;
        vector<vector<int>> g, tree;
        vector<int> cmp;
        TwoEdgeConnectedComponent(const vector<vector<int>> &g) : g(g) {
                n = (int) g.size();
                cmp.assign(n, -1);
        }
        void build() {
                LowLink lnk(g);
                lnk.dfs(0, -1);
                int k = 0;
                function<void (int, int)> dfs = [&](int u, int prev) {
                        cmp[u] = k;
                        for (auto v : g[u]) if (cmp[v] == -1 && lnk.bridge.count({min(u, v), max(u, v)}) == 0) {
                                dfs(v, u);
                        }
                };
                for (int i = 0; i < n; i ++) if (cmp[i] == -1) {
                        dfs(i, -1);
                        k ++;
                }
                tree.resize(k);
                for (auto e : lnk.bridge) {
                        tree[cmp[e.first]].push_back(cmp[e.second]);
                        tree[cmp[e.second]].push_back(cmp[e.first]);
                }
        }
};

以下のような問題が簡潔に実装できます。
D - 旅行会社高橋君

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        TwoEdgeConnectedComponent tecc(g);
        tecc.build();
        LCA lca(0, tecc.tree);
        int q;
        scanf("%d", &q);
        while (q --) {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);
                a --, b --, c --;
                if (lca.dist(tecc.cmp[a], tecc.cmp[b]) + lca.dist(tecc.cmp[b], tecc.cmp[c]) == lca.dist(tecc.cmp[a], tecc.cmp[c])) {
                        printf("OK\n");
                } else {
                        printf("NG\n");
                }
        }
        return 0;
}