素集合データ構造
Disjoint Sets
互いに素な集合
1つの要素が複数の集合に属することがない集合に分類して管理するためのデータ構造
makeSet(x)
要素がxただ一つである新しい集合を作る
findSet(x)
要素x が属する集合の代表の要素を求める
計算量は木の高さに依存
一回の実行あとは計算量縮小のため経路圧縮(path compression)が行われる
= 各ノードが親へのポインタを持つ
unite(x, y)
指定された2つの要素x, yを合併する
木の高さに従って合併方法を決める
高さは、rankという変数に記録
高さが低い方の木を高い方の木に合併させる
同じ場合は、合併後の代表のrankを一つ増やす
code:python
class DisjointSet():
def __init__(self, size):
self.size = size
self.parents = None * size for i in range(size):
self.makeSet(i)
def makeSet(self, x):
def findSet(self, x):
self.parentsx = self.findSet(self.parentsx) def same(self, x, y):
return self.findSet(x) == self.findSet(y)
def unite(self, x, y):
self.link(self.findSet(x), self.findSet(y))
def link(self, x, y):
if self.rankx > self.ranky: else:
if self.rankx == self.ranky: アニメーション