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

ゆらのふなびと

競プロ, Python, C++

Union-Find木の参考になるサイトと例題

競プロ UnionFind

Union-Find木を勉強するために使ったサイトと例題をまとめておきます。

「Union-Find木って何?」「とりあえずUnion-Find木を使えるようになりたい!」という人向けです。

Union-Find木とは?

Union-Find木はグループ分けを管理するデータ構造です。各グループを木構造で表現することで以下の2つが高速に可能になります。

  • 要素x, yが同じグループに属するかどうかの判定
  • 要素xの属するグループと要素yの属するグループの併合

ただしUnion-Find木は、「併合」「追加」はできても「分割」はできません。ここ注意。

詳しくは↓の解説スライドを読みましょう。これを読みながら実装すると問題が解けるようになっています。

ただし↑のUnion-Find木はあくまで簡易版です。↓のめぐるちゃんのツイートで実装すると「グループ内の要素数を求める」「グループ併合のときに大きい方に小さい方をつける(木を平坦にするため)」が可能になります。ひとつの配列uni[]を正のときと負のときで使い分けているのが賢いですね。これも実装して↑の問題を通してみましょう。

例題

「実際Union-Findってどんな感じで使うの?」という感触をつかむのによさそうな問題を以下に2つあげておきます。

+αの部分は注釈でヒントをつけておいたので、行き詰ったら使ってください。

Union-Findがあればほぼ瞬殺。(ヒント:*1

公式の解説ではDFSとなっていますが、Union-Find木を使うと割と何も考えずに解けます。(ヒント:*2

さらに練習したい人へ

もっとUnion-Find木を使いたい!という人のためのリンク集。(将来の自分のためも含め)

ページ下の方に類題がたくさん。

Union-Find木、実はいろいろ使えるらしい……?

クラスカル法との関連について。

*1:グループの個数がわかれば、それらをつなぐのに必要な最小の道の本数がわかります。グループの個数は親の個数と同じです。これはuniを走査することでわかるはず!

*2:Union-Findでグループ分けをしたら、各グループについて木かどうかの判定をしていきます。この判定はグループ内の辺の本数を見れば可能です