はまやんはまやんはまやん

hamayanhamayan's blog

1 or 2 [AtCoder Beginner Contest 126 E]

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;
}