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

ランダムな全域木を作る

上記の通りランダムな全域木を作る。

問題作る時とか、コンテスト中にでっかいケースを試したい時とかに

大きな全域木のサンプルデータを作ってくれるのを作ったのでメモっときます。

↓ソース(0_index)

何気に初めて pythonをいじった。

綺麗じゃないしめっちゃ長い(あとでc++で書いたやつもあげるかも)

やってることは以下の通り

f:id:satelliteyezu:20140907212030p:plain

まず、各ノードから一本ずつテキトーな場所にエッジを貼ります。

この時、自分にエッジを張るのはダメで
すでにとこかから、エッジが伸びてきている奴はエッジを貼ってはいけない

f:id:satelliteyezu:20140907212038p:plain

さきほどのエッジを張る過程でUnionFind木に集合を処理させとくとこんな感じになるので、それぞれの集合の代表を取り出す。

f:id:satelliteyezu:20140907212042p:plain

取り出したものに対し最初と同じように、各ノードからエッジを生やす。


毎回最悪でも集合の数が1/2ずつなっていくので最終的にすべてが同じになるまでの
この処理を繰り返す回数はたかだかLogNくらいなのでO(N Log N)でランダムな木が作れる…はず

なんかUnionfindした時に親となる木にエッジが偏るような気もするけどあんま気にしない

一直線とか1つのノ―ドから大量にエッジが生えてるような奴は自力で作ったほうが早い。

以上です。