AtCoder Beginner Contest 126：E - 1 or 2

問題
解法
解答

問題

https://atcoder.jp/contests/abc126/tasks/abc126_e

解法

(X_i, Y_i) のカードは他方が分かればもう片方もわかる関係である．なので，(a, b), (b, c) とあったとき a が分かれば b も c も同時にわかる．このようなカードの連結成分内のカードは 1 つのカードのみ魔法を使って知ることで全て知ることができる．よって，答えは連結成分数になる．Union-Find 木などを使って実装して O(N + M)．