この記事で使うデータ構造
Union-Find
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc075/tasks/abc075_c
この問題はUnion-Findと呼ばれるデータ構造で解くことができます。
方針
解説PDFの通り、
この問題のようなグラフの連結判定にはBFS
、DFS
、ワーシャルフロイド法
、Union-Find
など様々な方法で解けますが、この記事ではUnion-Find
で解きます。
Union-Findとは
互いに素なデータ集合を管理するためのデータ構造です。Union-Find
は以下の二つの機能を持っています。
union
二つの集合を併合するfind
指定した要素がどの集合に属するかを判定する
データ構造そのものはdisjoint-set
と呼び、それに対する操作をUnion-Find
と呼ぶ場合もありますが、この記事ではデータ構造をUnion-Find
と呼ぶことにします。
コード
1 | class UnionFind: |
記事情報
- 投稿日:2020年5月6日
- 最終更新日:2020年5月8日