pythonリストベースのルックアップセット実装テンプレート

class UnionFind:
    def __init__(self, n::
        self.father = list(range(n))
        self.size = [1] * n
        self.n = n
        #         
        self.setCount = n
    
    def find(self, x):
        if self.father[x] == x:
            return x
        self.father[x] = self.find(self.father[x])		
        return self.father[x]

    
    def merge(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.father[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def is_connected(self, x, y):
        return self.find(x) == self.find(y)