Atcoder ARC37[B] バウムテスト

union-find木の典型題。必ず得点したい。

解説

union-find木は2分探索木と並ぶ必修データ構造で、要素ごとのグループ分けを表現する木構造である。ある要素とある要素の親が同じなら、それは同じグループとして扱われる。

union-find木自体は難しくない。が、2分探索木とは違ってC++にライブラリ実装がないことがネックになる。使用のためには自分で解答上に表現しておく必要がある。

現実的には既存の実装を引用して利用することになる。もっとも広く利用されていると思われるのは蟻本実装p84で、上のコードはmain関数以外のサブルーチン群にあたる。

find(int x) インデックスxの親のインデックスを返す。

unite(int x,int y) ノードx,yを併合する。

どちらもグローバル配列のインデックスの、しかもint型を引数として取っている。競プロでのグローバルスコープ利用の慣習上、find()やunite()の見通しが悪くなりやすい。また添字インデックスの辻褄合わせも忘れずに。

上からエッジをunion-findに読み込んでいき、もしすでに連結しているノード群についての情報が入ってきたらそれをマークしておく。最後にそれらのマークを集計してめでたくACとなる。

samayotta.show()