問題
https://atcoder.jp/contests/abc097/tasks/arc097_b
考察
- 交換可能なら同じグループとする
- 同じグループというのを木で表す(値が同じなら同じグループ)
- Union Find木
ミスしたところ (UF)
- グループをまとめるとき(Union時)、自分の親を書き換えるのではなく、自分の根を書き換えるのが正しい
2020/10/30
- 今ならライブラリ化したもの or AtCoder Libraryを使うのでUFを実装することはない
- AC https://atcoder.jp/contests/abc097/submissions/17724509