class Coloring_Union_Find(): __slots__=("n", "parents", "rank", "data", "merge", "__group_number") def __init__(self, N, merge, unit): """ 0,1,...,N-1 を要素として初期化する. N: 要素数 merge: 合成の方法 e: 最初の値 """ self.n=N self.parents=[-1]*N self.data=[unit]*N self.rank=[0]*N self.merge=merge self.__group_number=N def find(self, x): """ 要素 x の属している族を調べる. x: 要素 """ V=[] while self.parents[x]>=0: V.append(x) x=self.parents[x] for v in V: self.parents[v]=x return x def union(self, x, y): """ 要素 x,y を同一視し, それぞれが持っている族の色を統合する. x,y: 要素 """ x=self.find(x) y=self.find(y) if x==y: return self.__group_number-=1 self.data[x]=self.data[y]=self.merge(self.data[x], self.data[y]) if self.rank[x]