【ABC126】E - 1 or 2 - メモ帳がわり

atcoder.jp

解法

偶奇にしか興味がないため、mod 2で考えてよい。

次のように場合分けして考える。

$Z_i ≡ 0　(mod　2)$ のとき

$A_{X_i}$ と $A_{Y_i}$ のどちらもが偶数、または奇数であることがわかる。
そのため、どちらかの偶奇が決定されると、もう片方の偶奇も自動的に判明する。

$Z_i ≡ 1　(mod　2)$ のとき

$A_{X_i}$ と $A_{Y_i}$ の片方が偶数で、もう片方が奇数であることがわかる。
こちらも、どちらかの偶奇が決定されると、もう片方の偶奇も自動的に判明する。

以上より、 $A_{X_i}$ と $A_{Y_i}$ の片方の数が判明すれば、もう片方の数もわかるため、連鎖的に数を特定していくことができる。
よって、UnionFindなどを使って連結成分数を数えれば、それが答えになる。

実装

// UnionFind構造体
struct UnionFind {
    vector<long long> par, siz;

    UnionFind(long long n) : par(n, -1) , siz(n, 1) { }

    // 根を求める
    long long root(long long x) {
        if (par[x] == -1) return x;
        else return par[x] = root(par[x]);
    }

    // x と y が同じグループに属するかどうか (根が一致するかどうか)
    bool issame(long long x, long long y) {
        return root(x) == root(y);
    }

    // x を含むグループと y を含むグループとを併合する
    bool unite(long long x, long long y) {
        x = root(x), y = root(y);
        if (x == y) return false; 
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }

    // x を含むグループのサイズ
    long long size(long long x) {
        return siz[root(x)];
    }
};

void solve(long long N, long long M, std::vector<long long> X, std::vector<long long> Y, std::vector<long long> Z){
    UnionFind Uf(N);
    REP (i, M) Uf.unite(X[i]-1, Y[i]-1);

    set<ll> st;
    REP (i, N) st.insert(Uf.root(i));

    c(st.size())
}