Union_Find (Disjoint Set Union) クラス in Python3

Share

とりあえずそこそこ形になったので、コードを。一応実コンテストでも使用してるので、そんなに間違いはないはず……。

2020/11/09 適当な拡張クラスを追加。グリッドのつながりをUnion Findで扱いたい時などに使えるかもしれない。

詳細については、下のスライドが詳しい。

以下、グラフとか頂点とか辺とかを使わないで平易に説明してみる。

砕けた言い方をすると、友達の友達は友達、という関係性の判定を簡単に行うためのものだ。AとB、BとC、CとD、DとEが友人であったとき、AとEが友人かどうか判定する際、通常の探索ならばA→B→C→D→Eとたどる必要がある。5人ならどうということは無いが、これが100人、1000人のグループが100個、1000個となるとその度に探索をするのは大変(=計算量が大)だ。

そこで、まず各グループに上司→部下、あるいは連絡網のような階層構造を設け、各人がどのグループにいるのかを簡単に問い合わせできるようにする。グループにA~Zの人がいるとしても、Zの上司はM、Mの上司はE、Eの上司はAで、Aはグループリーダー、といった感じで探索を進めようというイメージだ。これにより、対象が誰をリーダーとするグループにいるのかを簡単に(=少ない計算で)判定できる(階層構造なので、O(log N)となる)。

このようにした時、xとyが友達かどうか、つまり同じグループにいるかどうかを見るためには、要するにxのグループのリーダーとyのグループのリーダーが一致しているかどうかを見ればよいことになる。これなら簡単。やったぜ。

……だったら、最初っからグループの箱をつくって、その中にメンバーを放り込めばいい(あるいはグループのメンバーに名札をつければいい)んじゃない?と思うかもしれないが、そうすると、異なるグループのメンバー同士が友達になった時に困る。なぜなら、「その度に」どちらか片方のグループのメンバー全てを移動させる(あるいは名札をつけかえる)必要が出てくるからだ。これは効率が良くない。

Union Findにおいては、グループの併合を行う際も、片方のリーダーをもう片方のリーダーの下にくっつけることで、簡単にグループの併合を行うことができる。このやり方は、例えばAをリーダーとするグループとBをリーダーとするグループがある場合、Bに「今からAが上司になるから」と伝えるイメージである。これだけで済むので、非常に効率が良い。

つまり、Union Findとは、友達の友達はみんな友達になるグループ関係において、「xとyが同じグループにいるかどうかを判定する」「xとyを友達にする」という操作を、効率よく行えるようにするデータ構造・探索の仕組みというわけだ。

応用範囲は広く、グラフの連結問題・閉路の発見などはもちろん、例えば「嘘つきと正直者」のようなグループ分け問題に使用することもできる場合がある。

が、いちいち問題が出る度にイチから書くのは面倒なので、あらかじめ用意しておくと吉。というわけで、用意しておくことにしたのが、上記のコードである。
ネット上には他に良いコードがいくらでも落ちているが、冗長性を確保するという意味でも、上げておくことにする。

Share

コメントを残す

メールアドレスが公開されることはありません。