Union-Find木書いた

蟻本読んでたら出てきたのでC++からpythonにした。
同じ集合に所属するかどうか（Union-Find！）や、集合を合体するときに使う構造らしい。
練習問題も後日解いてみよう。

class UnionFindTree:
  def __init__(self, n):
    #親のノード番号を入れる。初期値はすべて異なるものにしておいた
    self.parent = [i for i in range(n+1)]
    #rankは木の高さを表す。簡単のため、下のノードを根につなぎなおしてもrankは変化させない
    self.rank = [0] * (n+1)
  
  #その木において、ｘがどのUnionに所属するか（根は何なのか）を判定する
  def findUnion(self, node_num):
    #親が根
    if self.parent[node_num] == node_num:
      return node_nunm
    else:
      #親が根ではないので親の親を調べるといつか根にたどり着く
      #一度探索したら次回からは探索しなくて済むように根に接続しておく
      self.parent[node_num] = self.findUnion(self.parent[node_num])
      return self.parent[node_num]
    
  def isSameUnion(self, x, y):
    #findUnionで両方の根を確かめて比べる
    return self.findUnion(x) == self.findUnion(y)
  
  def unite(self, x, y):
    x = self.findUnion(x)
    y = self.findUnion(y)
    
    if x == y:
      #根が同じなら何もしない
      return
    
    elif self.rank[x] < self.rank[y]:
      #高いほうの下に小さいほうを繋いで平衡に近い状態にする
      self.parent[x] = y
    elif self.rank[x] > self.rank[y]:
      self.parent[y] = x
    else:
      #高さが同じなので根にもう一方を繋いで、根のほうの高さが＋１される