Atcoder ARC37[B] バウムテスト
B: バウムテスト - AtCoder Regular Contest 037 | AtCoder
union-find木の典型題。必ず得点したい。
解説
- 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となる。
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (35件) を見る