こんにちは
PythonでのUnion-Find（素集合データ構造）の実装と使い方を参考にして
union findの使い方をみていきます。
アリ本にもでてくるデータ構造です。
上記リンクでの実装でのポイントはparentsで
親(parents)に各要素の親番号(親要素へのindex)を格納する要素自身が親つまりは根元の場合は、そのグループの要素数をマイナスで持つ
とうポイントを押さえれば、あとの理解は付いてくるはずです。
ここで少しバックグラウンドを話しましょう。
union findの祖先は
quick findです。coursera でプリンストン大学の動画はこちら
が、unionにO(N)で、実際グラフ形成にO(N^2)でquadratic(２乗)かかって 、データ大きいとだめだ
ってことで
union findです。っと行きたいところですが、まずはその前身、quick-unionを見ましょう。
union findっていうのも理解するには見ておいて損はないです。（coursera union find動画）
quick-unionはunionが速いので、すごい良さげやん！って思うんですがworseケースを考えるとまだquadraticなんですねー。
worseケースっていうのは、findのときに高〜い、一直線の木です。
そこで！
工夫をしたのが、やっときました。そうunion findです。
union-quickで、木が高いとworseになるということだったので、木を構成していくとき
つまりはunion時に木が高くならないような工夫をしましょう！というのが肝です
それをするためにはグループのノード数の数を保存しておけばいいんです
あと、もう一個の工夫、これも高さを出さないための、木を低く保つための工夫で
findの速さにつながることですね。これは経路圧縮(path compression）というもので
やはりこの動画が非常にわかりやすいです。さらに経路圧縮でさらにかなり、速くなります。
log*N（ログNスター）というか速さ、でリニア(O(N))に近い速さだそうです。
親(parents)に各要素の親番号(親要素へのindex)を格納する要素自身が親つまりは根元の場合は、そのグループの要素数をマイナスで持つ
実装
class unionfind():
def __init__(self, n):
self.n = n
self.pars = [-1] * n # 親のindexか、自信が親の場合は-(要素数)
def find(self, x):
if self.pars[x] < 0:
return x
else:
# 親が根元ではないので、根元を探す旅
oya = self.pars[x]
# #これが経路圧縮。なくてもうごくよ。有ると速い。
# self.pars[x] = self.find[oya]; return self.pars[x]
return self.find(oya)
def union(self, x, y):
X = self.find(x) # Xはxの親である
Y = self.find(y)
if X == Y: return
# 親のマージ。親のグループの小さい方に、大き方を足したいので。
if self.pars[X] > self.pars[Y]:
X, Y = Y, X
self.pars[X] += self.pars[Y]
self.pars[Y] = X
以上です