ABC126 E - 1 or 2

精進記録 / 解法メモ

問題

問題

提出コード

解法

カードを頂点としてグラフにみたてて、xi と yi に辺があるものとして連結な頂点をグループ分けし、そのグループの個数 + どのグループにも属していないカードの数を求めれば AC

グループの構築は UnionFind、グループの個数は Set を使って求めた。

考察

まず入力されたリストで一度も触れられてないカードについては判断材料がないのでそのようなカードについては必ずコストが必要とわかる。

偶奇の性質から、zi が何であっても、xi と yi の組みについてどちらかがわかればもう片方も判明することがわかる。よってカードを頂点としてグラフにみたてて、xi と yi に辺があるものとして、ある頂点から辺を辿ってたどり着ける頂点を同じグループと考えた時、そのようなグループの中でどれか一つが判明すれば連鎖的にグループ内の他のカードの数も判明するとわかる。

グループ分けについては UnionFind で実装すればそのあたりの処理はすべて超高速（ならしで逆アッカーマン関数とみなせる、logよりも速い）にできる。

あとはグループの個数と、一度も触れられてないカードの個数の和を求めればよい。

一度も触れられてないカードの個数については特に工夫は必要なく、 n が最大 $10^{5}$ なので普通に全部調べても間に合う。

グループの個数を求めるには、UniondFind では同じグループに所属する頂点は必ず共通する根を持つので UF 内の根の個数をすべて求めればよい。具体的には根を全列挙して uniq を取る。今回は適当に Set でやった。

感想

UnionFind とか偶奇の性質とかは大分慣れてきた実感がある。水色Diffだったけど、考察はわりとすぐできてちょっとした茶色Diffとかよりも簡単に感じた。

---

以上。オワリ😇