けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 304 E - Good Graph (緑色, 475 点)

AtCoder 緑色diff ABC-E 典型要素を詰め合わせた教育的問題 グラフ クエリ処理問題 クエリ(グラフ上) 連結成分 グラフのconnectivity グラフ上にチェックポイントのある問題 データ構造テク：差分更新 Yes/No判定問題 Union-Find データ構造テク：前処理 条件の言い換え 連結成分ごとに分解して考える N個のものうち1個を変更・削除したものを解く AtCoder475点

Union-Find 慣れしていれば解きやすい！

問題概要

頂点数 N、辺数 M の無向単純グラフ G が与えられる。

K 組の頂点対 (x_{1}, y_{1}), \dots, (x_{K}, y_{K}) について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。

与えられるグラフ G は良いグラフである。

このグラフに対して Q 個のクエリが与えられる。各クエリでは 2 個の頂点 p, q が指定される。これら 2 頂点を辺で結んだとき、グラフ G が良いグラフであるかどうかを判定してください。

制約

  • 2 \le N \le 2 \times 10^{5}
  • 0 \le M \le 2 \times 10^{5}

考えたこと

Union-Find はグループ分けを管理するデータ構造なのだが、各グループは根付き木で管理することを知っていれば、この問題は解きやすい。

つまり、各グループには 1 つ根があるのだ！！！

このことを念頭に置いて考察を進めていく。

頂点 p, q を結ぶ状況を考える

それでは、頂点 p, q を結ぶとき、どうなるかを考えよう。まず、頂点 p, q がすでに同じグループに属するときは、 p, q 間に辺を張っても、グラフの連結成分分解の状況に変化が生じないので、答えは "Yes" だ！

よって、頂点 p, q が異なるグループに属するとしよう。このとき、もし K 組の頂点対のうちの 1 つを (x, y) として、 p, q を結ぶことによって、 x, y が同じグループに属するようになってしまったら "No" だ。

つまり、

  • 頂点 p と頂点 x が同じグループにあって、頂点 q と頂点 y が同じグループにある
  • 頂点 p と頂点 y が同じグループにあって、頂点 q と頂点 x が同じグループにある

のいずれかを満たす場合には "No" となる。どの K 組の頂点対についても、上の条件を満たさなければ "Yes" となる。

判定を高速化

だいぶ整理できたけど、今のままではまだ各クエリごとに O(K \alpha(N)) の計算量を要するので TLE となる。

ここで、さっきの「各グループには根がある」ことを思い出そう。頂点 p, q, x, y の属するグループの根を r_{p}, r_{q}, r_{x}, r_{y} とすると、上の条件は簡単に書き直せるのだ。 r_{p} \le r_{q}, r_{x} \le r_{y} が成り立つように適宜 swap しておけば、

(r_{p}, r_{q}) = (r_{x}, r_{y})

と書き表せる。よって、あらかじめ K 組の頂点対について、 (r_{x}, r_{y}) を set 型変数などに格納しておくことで、パスが生じてしまうような頂点対があるかどうかを O(\log K) の計算量で判定できることがわかった。

全体として、 O(M \alpha(N) + Q \log K) の計算量で解ける。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

// Union-Find
struct UnionFind {
    // core member
    vector<int> par;

    // constructor
    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
    // debug
    friend ostream& operator << (ostream &s, UnionFind uf) {
        map<int, vector<int>> groups;
        for (int i = 0; i < uf.par.size(); ++i) {
            int r = uf.root(i);
            groups[r].push_back(i);
        }
        for (const auto &it : groups) {
            s << "group: ";
            for (auto v : it.second) s << v << " ";
            s << endl;
        }
        return s;
    }
};

int main() {
    // 入力
    int N, M, K, Q;
    cin >> N >> M;
    
    // Union-Find を作る
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        uf.merge(u, v);
    }
    
    // K 組の頂点対についての前処理
    cin >> K;
    vector<int> x(K), y(K);
    set<pint> S;
    for (int i = 0; i < K; ++i) {
        cin >> x[i] >> y[i];
        --x[i], --y[i];
        x[i] = uf.root(x[i]), y[i] = uf.root(y[i]);
        if (x[i] > y[i]) swap(x[i], y[i]);
        S.insert(pint(x[i], y[i]));
    }
    
    // クエリ処理
    cin >> Q;
    while (Q--) {
        int p, q; cin >> p >> q; --p, --q;
        p = uf.root(p), q = uf.root(q);
        if (p > q) swap(p, q);
        if (!uf.same(p, q) && S.count(pint(p, q))) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}