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

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

AtCoder ABC 126 E - 1 or 2 (水色, 500 点)

これまた Union-Find を用いる教育的問題!!!!!

問題へのリンク

問題概要

 N 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 N 枚のカードの数値  A_1, A_2, \dots, A_N をすべて当てたい。

現在、以下の形式をした条件が  M 個与えらている:

  • 整数  x, y, z に対して、 A_x + A_y + z は偶数である

これらの条件は互いに矛盾がないことはわかっている。このとき、 N 枚のカードから何枚か選んでその中身を見ることができる。最小で何枚のカードを見れば、すべてのカードの中身を当てることができるかを求めよ。

制約

  •  2 \le N \le 10^{5}
  •  1 \le M \le 10^{5}
  •  1 \le x \gt y \le N

考えたこと

要するに

  • 各カードの値が偶数なのか奇数なのかだけを知りたい

ということが言える。こういう問題では、 {\rm mod}. 2 ですべてを考えるとよい。われわれにあたえられた条件は

  •  A_{x} + A_{y} ≡ 0  {\rm or }  1 ({\rm mod}. 2)

という形をしたものが  M 個与えられるということになる。この条件は一体何を意味しているのだろうか??

条件式の意味

例えば

  •  A_2 + A_5 ≡ 0  {\rm or }  1

という条件があったとき、

  •  A_2 が偶数か奇数かがわかったら、 A_5 についてもわかるし、
  •  A_5 が偶数か奇数かがわかったら、 A_2 についてもわかる、

という関係にあることがわかる。では

  •  A_x + A_y ≡ 0  {\rm or }  1
  •  A_y + A_z ≡ 0  {\rm or }  1

という 2 つの関係式があったらどうなるであろう...これは、「 A_x, A_y, A_z のうちどれか 1 つでも偶奇かがわかれば、3 つすべての偶奇がわかる」ということになる。よってわれわれはノードが  1, 2, \dots, N のグラフを用意して、  M 個の  A_x, A_y に関する条件に対して

  • ノード  x とノード  y との間に辺を張ったグラフを用意したとき、
  • 各連結成分については、どれか 1 個でも偶奇がわかれば、連結成分内のすべてのノードの偶奇がわかる

ということになる。注意点として例えば

  •  A_1 + A_2 ≡ 0
  •  A_2 + A_3 ≡ 0
  •  A_1 + A_3 ≡ 1

のような関係式があったら、これらは矛盾し合っていて、これを満たす解は存在しない。でもそのようなことは起こらないことが問題文から保証されている。ただし

  •  A_1 + A_2 ≡ 0
  •  A_2 + A_3 ≡ 0
  •  A_1 + A_3 ≡ 0

のような関係式の組はありうる。つまり 3 本目の式は 1 本目と 2 本目から導かれるので冗長なのだ。この 3 本のうちの 2 本だけでよい。でもこういうのは問題ない。

問題の答え

以上の考察から「上のように作ったグラフの連結成分の個数」が答えであることがわかった。これは例えば Union-Find でパッと求めることができる。

Union-Find 使って連結成分数出す方法

意外とここが詰まる方も多い気がする。実際はとても簡単で Union-Find というのは

  • 同じ連結成分にあるノード間では root の値が等しい
  • 異なる連結成分にあるノード間では root の値が異なる

という性質を満たすものであったことを思い出す。そうすると、ノード  v = 1, 2, \dots, N に対して root(v) を求めてあげて、その種類が何通りあるかを見れば OK。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(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)];
    }
};

int main() {
    int N, M; cin >> N >> M;
    vector<int> X(M), Y(M), Z(M);
    for (int i = 0; i < M; ++i) cin >> X[i] >> Y[i] >> Z[i], --X[i], --Y[i];
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) uf.merge(X[i], Y[i]);
    set<int> se;
    for (int i = 0; i < N; ++i) se.insert(uf.root(i));
    return (int)se.size();
}