ABC126 E - 1 or 2 - ツバサの備忘録

解法

$A_{X_{i}}$ を指定してその数字を特定したとします。
すると、 $A_{Y_{i}}$ は $Z_{i}$ の偶奇に関わらず、自動的に数字が特定できます。
そして、これが連鎖的に続くことになり、
他に $A_{X_{i}}, A_{Y_{i}}$ が条件に含まれている部分についても自動的に、もう片方が特定されていきます。
ので、結局は $A_{X_{i}},A_{Y_{i}}$ という条件は、その2つの頂点を繋ぐ辺が存在している、と考えると、 $N$ 頂点のグラフの連結成分の個数を求める問題になり、これはUnion-Findを利用して、与えられた辺を結び付けていくことで、うまく個数を数えられるようになります。
答えは、 $root(i) = i$ となっている $i$ の個数を求めればいいです。
自分は、 $i$ について全探索をし、 $root(i)$ が初登場のときにカウント、そうでなければスルー、という感じでカウントをしました。

感想

はじめは $A_{Z_{i}}$ だと思っていました。
$Z_{i}$ が今回の問題にほぼ無関係であることがわかってからはすぐだったので良かったと思います。