class UnionFind: # 初期化 nは要素数 def __init__(self,n): # 全体の大きさ self.n=n # -x:グループのサイズ(自身が根),k(正):根がk self.parent_size=[-1]*n # 要素の根を返す def leader(self,a): # aが根ならa自身を返す if self.parent_size[a]<0: return a # aが根でないなら根に向かって木をたどる+根の更新 self.parent_size[a]=self.leader(self.parent_size[a]) # 根を返す return self.parent_size[a] # aとbを結合 def merge(self,a,b): # a,bの根をx,yへ x,y=self.leader(a),self.leader(b) # 根が同じなら終了 if x == y: return # グループのサイズ=要素数を比較 サイズの小さい方を大きい方につなげるため # x