ABC126 E - 1 or 2

問題原文

atcoder.jp

問題要旨

枚のカードが裏向きに置かれている。各カードには 1 または 2 が書かれている。
また「 番目のカードと 番目のカードに を加えた値は偶数」という情報が 個与えられる。
最低何枚のカードをめくれば、全てのカードについて書かれている数を当てることができるか？

• 
• 
• 

解法

まず、 の値はどうでもいい。つまり、各情報は 「 番目のカードと 番目のカードの和の偶奇を知れると」して良い。
また、 番目のカードがわかれば、 各カードに書かれている数は 1 か 2なのだから、結局 番目のカードもわかる。
そして、 番目のカードがわかれば、 番目に紐づく情報を持つカードの情報は、結局芋づる式にわかってしまう。

結局求めたいのは、「情報が連鎖していくグループがいくつあるか？」になったので、これはUnionFindなどを用いて数えればよい。

実装

N, M = map(int, input().split())

UF = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    x, y = x - 1, y - 1
    UF.union(x, y)
UF.all_find()  # 全ノードについてfind
 
print(len(set(UF.par)))

感想

本番5分とかで思いついたらしい。
UFだいすき！