AtCoder ABC120 D問題の解法(Union−Find)を図示してみる
AtCoder ABC120のD問題で解法とされたUnion-Find木について。
茶色(当時)の私でも分かるように絵を書いて処理を追ってみた。
理屈やコードは素晴らしい記事があったのでリンク先参照。
本記事ではABC120のD問題を具体例として「実際どう動いているか」を図示して分かりやすく示します。
Union−Find構造とは
www.slideshare.net chokudaiさんによる解説スライドがとても分かりやすい。
分かりやすすぎてこの記事の存在意義が謎だけど、私の理解のために…
キーワードだけ拾うと、Union−Find木は
- 要素をグループに分類するための構造 ※分割はできない
- 以下の工夫で計算量はO(α(n)) ※O(log(n))より早いらしい
- 経路圧縮
- ランク付け
Pythonコード
juppy.hatenablog.com こちらのコードがとても分かりやすかったので、参考にさせていただきました。
どう動いてるのか
ABC120のD問題はザックリ言うと、
N個の島とM本の橋があり、橋が結んでいる島の組がAi, Biとして与えられる。
橋が一つずつ崩落していったとき、「行き来できなくなった島の組」はいくつか？
という問題。
解法として、逆作業として橋を一つずつ架けたときの「行き来できる島の組」を考える。
「島をグループに統合していく」ので、Union-Findそのもの。
コレを入力例1（島5個、橋4本）を例として図示する。
D問題の回答としては、Union−Find木を構築したときの不便さを逆順に出力すればOK。
数学的なセンスや経験があれば解説や数式からこういうイメージが持てるのかもしれないけど、
残念ながら私には無理なので、問題の度にこうやってお絵かきして理解してます…
数学は苦手だけど競プロとか機械学習は楽しい、みたいな初学者の助けになれば幸いです。
（経路圧縮とかランクについても図に書くつもりでしたが力尽きたので、いずれ…）
