Union Find

并查集模板

class Solution:
    
    def initialize(self, n):
        self.father = {i: i for i in range(n)}
            
    def union(self, id1, id2):
        self.father[self.find(id1)] = self.find(id2)

    def find(self, idx):
        path = []
        while idx != self.father[idx]:
            path.append(idx)
            idx = self.father[idx]
            
        for id in path:
            self.father[id] = idx
            
        return idx