読者です 読者をやめる 読者になる 読者になる

samayotta.show()

好きな映画は『たまこラブストーリー』です。

Atcoder ARC37[B] バウムテスト

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder

 

ARC37B.バウムテスト

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

 

解説

  • union-find木

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

pakapa104.hatenablog.com

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

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

  • 使用上の手引と注意

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

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

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

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

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?