UnionFind
code: UnionFind.py
class UnionFind:
def __init__(self, n):
self.parents = list(range(n))
def find(self, i):
# 自分自身だったらそのまま返す
return i
else:
# 自分の祖先を、自分の祖先の祖先で更新する
# こうすることで、途中を飛ばすことができる
self.parentsi = self.find(self.parentsi) def union(self, i, j):
i = self.find(i)
j = self.find(j)
if i != j:
i, j = min(i, j), max(i, j)