AtCoder ABC120 D問題の解法(Union−Find)を図示してみる - y_megane.log

AtCoder ABC120のD問題で解法とされたUnion-Find木について。 茶色(当時)の私でも分かるように絵を書いて処理を追ってみた。 理屈やコードは素晴らしい記事があったのでリンク先参照。 本記事ではABC120のD問題を具体例として「実際どう動いているか」を図示して分かりやすく示します。 atcoder.jp Union−Find構造とは Union find(素集合データ構造) from AtCoder Inc. www.slideshare.net chokudaiさんによる解説スライドがとても分かりやすい。 分かりやすすぎてこの記事の存在意義が謎だけど、私の理解のために… キーワードだけ拾うと、Union−Find木は 要素をグループに分類するための構造 ※分割はできない 以下の工夫で計算量はO(α(n)) ※O(log(n))より早いらしい 経路圧縮 ランク付け Py