ABC126 E - 1 or 2

April 16, 2020

競技プログラミング

AtCoder, UnionFind, グラフ

問題

問題リンク

考えたこと

問題を読み間違えたし, さっぱりできなかった

解説をみる

グラフ問題らしい..

(A[x[i]] + A[y[i]] + Z[i]) % 2 == 0であり、かつ必ず矛盾がない
式を移行すると
(A[x[i]] + A[y[i]]) % 2 == Z[i] % 2
このときAが取れる値は1か2だけなので

Z[i]が奇数であればA[x[i]], A[y[i]] = {1,2} or {2,1}
Z[i]が偶数であればA[x[i]], A[y[i]] = {1,1} or {2,2}

つまり, A[x[i]], A[y[i]] のどちらかが分かればもう片方の値もわかるということ
さらにいうと,

x=1, y=2, z=1
x=2, y=3, z=1
x=3, y=4, z=2
x=5, y=6, z=2

という4つの入力があったとして、1番目のカードの番号が確定すれば、上で証明したように
1つ目の入力から2番目のカードの番号も確定する
さらに2番目のカードがわかったので,2番目の入力から、3番目のカードがわかり,さらにそれより4番目のカードもわかる
5,6番目のカードはわからないので、5番目のカードをめくる。
すると4番目の入力から6番目のカードがわかる

これより連鎖しているカード(グラフでいうと同じ木に属する頂点)のうち1つが分かれば、そのグループ内の全てがわかる
(制約から、入力データで矛盾がないことが保証されているので)

これから答えとしてはUnionFind木を構築して、グループ数=めくる必要があるカード枚数となる

UnionFindについてはこちらに少しまとめてみてる

提出したコード

提出リンク

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

typedef pair<int, int> P;
ll modnum = 1e9+7;

struct UnionFind {
    // parで親のnode値と、サイズを同時に管理する。
    // 根ではないnodeのparは親となるnodeの値が入ってる
    // 根にはサイズ数が入っている。区別できるようにサイズはマイナスの値で入っている
    // そのため、初期値はすべて-1になる(mergeの際にmergeされる側の根に、mergeする方の根が加算される
    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;
        return par[x] = root(par[x]);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        // サイズが大きいほうにマージする
        // 以下は必ずxが大きいほう(サイズはマイナスの値が入ってるので)にするように調整している
        if (par[x] > par[y]) swap(x, y);
        // xのサイズに、yのサイズを加算する
        par[x] += par[y];
        // yの根をxに更新する
        par[y] = x;
        return true;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int n,m; cin >> n >> m;
    UnionFind tree(n);
    vector<int> x(m);
    vector<int> y(m);
    vector<int> z(m);

    // UnionFind構築
    rep(i, m) {
        int x,y,z; cin >> x >> y >> z;
        x--;
        y--;
        z--;
        tree.merge(x,y);
    }

    // グループ数の確認
    set<int> ans;
    rep(i, n) {
        ans.insert(tree.root(i));
    }

    cout << ans.size() << endl;

    return 0;
}