https://atcoder.jp/contests/abc126/tasks/abc126_e
前提知識
解説
https://atcoder.jp/contests/abc126/submissions/5476491
入力には矛盾が無いということが使える。
あるiについて、Axi+Ayi+Ziが偶数であることが分かるとき、xiとyiに辺を張ることを考える。
この辺の意味は片方がわかれば、もう片方も分かるという意味である。
このルールで辺を貼っていくと、無向グラフができあがる。
この無向グラフの連結成分について、1つでも数がわかれば全ての数が特定できる。
つまり、連結成分の数が答えになっている。
連結成分を探すのはUnionFindを使えばいいので、使って連結成分数を数えると答え。
int N, M; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; UnionFind uf(N); rep(i, 0, M) { int x, y, z; cin >> x >> y >> z; x--; y--; uf(x, y); } int ans = 0; rep(i, 0, N) if (uf[i] == i) ans++; cout << ans << endl; }