yukicoder No.1326 ふたりのDominator (4D)

二重頂点連結成分分解して得られる Block-Cut 木のクエリに答えていく問題。

• 問題へのリンク

問題概要

頂点数 、辺数 の連結な単純無向グラフが与えられる。次の 回のクエリに答えよ。

【クエリ】
各クエリでは 2 頂点 が与えられる。 個の頂点のうち、次の条件を満たすものの個数を求めよ。

• ではない
• その頂点をグラフから削除すると、2 頂点 が異なる連結成分に含まれるようになる

制約

• 
• 
• 

考えたこと

「頂点を削除する」という削除モードの下でグラフの connectivity を考えたいとき、二重頂点連結成分分解すると良いことが多い。二重頂点連結成分分解して、Block-Cut 木を作ろう。このとき、次のように整理できる。

---

• 頂点 がともに関節点ではないとき：
  • Block-Cut 木上の、 の属する連結成分に対応する 2 頂点間のパスの長さを として、 が答えである
• 頂点 が関節点で、頂点 が関節点でないとき：
  • Block-Cut 木上の、関節点 に対応する頂点と、 の属する連結成分に対応する頂点を結ぶパスの長さを として、 が答えである
• 頂点 が関節点でなく、頂点 が関節点であるとき：
  • 上と同様
• 頂点 がともに関節点であるとき：
  • Block-Cut 木上の、関節点 に対応する頂点を とする
    • のとき：答えは 0
    • それ以外のとき： を結ぶパスの長さを として、 が答えである

---

パスの長さは、たとえば LCA などで求められる。その場合、計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;


// Edge Class
template<class T> struct Edge {
    int from, to;
    T val;
    Edge() : from(-1), to(-1), val(-1) { }
    Edge(int f, int t, T v = -1) : from(f), to(t), val(v) {}
    friend ostream& operator << (ostream& s, const Edge& e) {
        return s << e.from << "->" << e.to;
    }
};

// graph class
template<class T> struct Graph {
    vector<vector<Edge<T>>> list;
    
    Graph() { }
    Graph(int n) : list(n) { }
    Graph(const Graph<T> &G) : list(G.list) { }
    void init(int n) {
        list.assign(n, vector<Edge<T>>());
    }
    Graph &operator = (const Graph &g) {
        list = g.list;
        return *this;
    }

    const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
    const size_t size() const { return list.size(); }
    const void clear() {
        list.clear();
    }
    const void resize(int n) {
        list.resize(n);
    }

    void add_edge(int from, int to, T val = -1) {
        list[from].push_back(Edge(from, to, val));
        list[to].push_back(Edge(to, from, val));
    }

    friend ostream &operator << (ostream &s, const Graph &G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << " -> ";
            for (const auto &e : G[i]) s << e.to << " ";
            s << endl;
        }
        return s;
    }
};

// low-link
template<class T> struct LowLink {
    // results
    vector<int> ord, low;
    vector<int> aps;         // articulation points
    vector<Edge<T>> brs;     // brideges

    // constructor
    LowLink() { }
    LowLink(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // solver
    int dfs(const Graph<T> &G, int t, int v, int p) {
        ord[v] = low[v] = t++;
        int num_of_children = 0;
        bool exist_articulation = false, is_multiple_edge = false;
        for (const auto &e : G[v]) {
            if (ord[e.to] == -1) {
                num_of_children++;
                t = dfs(G, t, e.to, v);
                low[v] = min(low[v], low[e.to]);  // forward edge of DFS-tree
                exist_articulation |= (p != -1) && (low[e.to] >= ord[v]);
                if (ord[v] < low[e.to]) brs.push_back(e);
            } else if (e.to != p || is_multiple_edge) {
                low[v] = min(low[v], ord[e.to]);  // back edge
            } else {
                is_multiple_edge = true;
            }
        }
        if (exist_articulation || (p == -1 && num_of_children > 1)) {
            aps.emplace_back(v);
        }
        return t;
    }

    void solve(const Graph<T> &G) {
        ord.assign(G.size(), -1), low.assign(G.size(), -1);
        for (int v = 0, k = 0; v < (int)G.size(); v++) {
            if (ord[v] == -1) k = dfs(G, k, v, -1);
        }
    }
};

// BiConnected Components decomposition
// block-cut tree (aps: 0, 1, ..., A-1, components: A, A+1, ..., A+C-1)
// (A: size of aps, C: num of components)
template<class T> struct BiConnectedComponentsDecomposition {
    // result
    LowLink<T> ll;
    vector<int> id_ap;   // index of the articulation point (size: V)
    vector<int> id_cc;   // index of the connected component (size: V)
    vector<vector<int>> groups;   // biconnected components (size: C)
    vector<vector<int>> tree;     // block-cut tree (size: A + C)

    // intermediate results
    vector<int> seen, finished;
    vector<vector<pair<int, int>>> grouped_edges;
    vector<pair<int, int>> tmp_edges;

    // constructor
    BiConnectedComponentsDecomposition() { }
    BiConnectedComponentsDecomposition(const Graph<T> &G) {
        solve(G);
    }
    void init(const Graph<T> &G) {
        solve(G);
    }

    // getter, original graph to block-cut tree (v: node of orignal graph)
    int is_ap_original_graph(int v) const {
        return (id_ap[v] != -1);
    }
    int get_id(int v) const {
        return (id_ap[v] == -1 ? id_cc[v] : id_ap[v]);
    }

    // getter, block-cut tree to orignal graph（v: node-id of block-cut tree)
    int is_ap(int v) const {
        return (v < ll.aps.size());
    }
    int get_ap(int v) const {
        if (v >= (int)ll.aps.size()) return -1;  // not ap
        else return ll.aps[v];
    }
    int get_size(int v) const {  // including aps
        if (v < (int)ll.aps.size()) return 1;  // ap
        else return groups[v - ll.aps.size()].size();
    }
    vector<int> get_group(int v) const {
        if (v < (int)ll.aps.size()) return vector<int>({ll.aps[v]});  // ap
        else return groups[v - ll.aps.size()];
    }

    // solver
    void dfs(const Graph<T> &G, int v, int p) {
        seen[v] = true;
        if (G[v].empty()) {
            groups.emplace_back(vector<int>({v}));
        }
        for (const auto &e : G[v]) {
            if (e.to == p) continue;
            if (!seen[e.to] || ll.ord[e.to] < ll.ord[v]) {
                tmp_edges.emplace_back(minmax(v, e.to));
            }
            if (!seen[e.to]) {
                dfs(G, e.to, v);
                if (ll.low[e.to] >= ll.ord[v]) {
                    groups.emplace_back(vector<int>({v}));
                    grouped_edges.emplace_back();
                    int ap = v;
                    while (!tmp_edges.empty()) {
                        const auto &e2 = tmp_edges.back();
                        if (!finished[e2.first] && e2.first != ap) {
                            groups.back().emplace_back(e2.first);
                            finished[e2.first] = true;
                        }
                        if (!finished[e2.second] && e2.second != ap) {
                            groups.back().emplace_back(e2.second);
                            finished[e2.second] = true;
                        }
                        grouped_edges.back().emplace_back(e2);
                        tmp_edges.pop_back();
                        if (e2.first == min(v, e.to) && e2.second == max(v, e.to)) break;
                    }
                }
            }
        }
    }

    void solve(const Graph<T> &G) {
        ll.init(G);
        seen.assign(G.size(), false), finished.assign(G.size(), false);
        for (int v = 0; v < (int)G.size(); v++) {
            if (!seen[v]) dfs(G, v, -1);
        }
        id_ap.assign(G.size(), -1), id_cc.assign(G.size(), -1);
        for (int i = 0; i < (int)ll.aps.size(); i++) {
            id_ap[ll.aps[i]] = i;
        }
        tree.assign(ll.aps.size() + grouped_edges.size(), vector<int>());
        vector<int> last(G.size(), -1);
        for (int i = 0; i < (int)grouped_edges.size(); i++) {
            vector<int> st;
            for (auto [u, v] : grouped_edges[i]) {
                st.push_back(u), st.push_back(v);
            }
            for (auto v : st) {
                if (id_ap[v] == -1) {
                    id_cc[v] = i + ll.aps.size();
                } else if (last[v] != i) {
                    tree[i + ll.aps.size()].push_back(id_ap[v]);
                    tree[id_ap[v]].push_back(i + ll.aps.size());
                    last[v] = i;
                }
            }
        }
    }
};

struct LCA {
    using Graph = vector<vector<int>>;
    vector<vector<int> > parent; // parent[d][v] := 2^d-th parent of v
    vector<int> depth;
    LCA() { }
    LCA(const Graph &G, int r = 0) { init(G, r); }
    void init(const Graph &G, int r = 0) {
        int V = (int)G.size();
        int h = 1;
        while ((1<<h) < V) ++h;
        parent.assign(h, vector<int>(V, -1));
        depth.assign(V, -1);
        dfs(G, r, -1, 0);
        for (int i = 0; i+1 < (int)parent.size(); ++i)
            for (int v = 0; v < V; ++v)
                if (parent[i][v] != -1)
                    parent[i+1][v] = parent[i][parent[i][v]];
    }
    void dfs(const Graph &G, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto e : G[v]) if (e != p) dfs(G, e, v, d+1);
    }
    int get(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = 0; i < (int)parent.size(); ++i)
            if ( (depth[v] - depth[u]) & (1<<i) )
                v = parent[i][v];
        if (u == v) return u;
        for (int i = (int)parent.size()-1; i >= 0; --i) {
            if (parent[i][u] != parent[i][v]) {
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }
};

int main() {
    int N, M, Q, u, v, x, y;
    cin >> N >> M;
    Graph<int> G(N);
    for (int i = 0; i < M; i++) {
        cin >> u >> v, u--, v--;
        G.add_edge(u, v);
    }

    BiConnectedComponentsDecomposition<int> bcc(G);
    auto tree = bcc.tree;
    LCA lca(tree);

    cin >> Q;
    while (Q--) {
        cin >> x >> y, x--, y--;
        int xid = bcc.get_id(x), yid = bcc.get_id(y);
        int l = lca.get(xid, yid);
        int len = lca.depth[xid] + lca.depth[yid] - lca.depth[l] * 2;

        int apnum = 0, res = 0;
        if (bcc.is_ap_original_graph(x)) apnum++;
        if (bcc.is_ap_original_graph(y)) apnum++;


        if (apnum == 0) res = len / 2;
        else if (apnum == 1) res = (len - 1) / 2;
        else res = len / 2 - 1;
        res = max(res, 0);
        cout << res << endl;
    }
}