• + 0 comments
    class DisjointSet:
        def __init__(self, arr = []):
            self.parent = {x : x for x in arr}
            self.rank = {x : 0 for x in arr}
            self.size = {x : 1 for x in arr}
    
        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        
        def union(self, x, y):
            if x not in self.parent:
                self.parent[x] = x
                self.rank[x] = 0
                self.size[x] = 1
    
            if y not in self.parent:
                self.parent[y] = y
                self.rank[y] = 0
                self.size[y] = 1
    
            rootX = self.find(x)
            rootY = self.find(y)
    
            if rootX != rootY:        
                if self.rank[rootX] > self.rank[rootY]:
                    self.parent[rootY] = rootX
                    self.size[rootX] += self.size[rootY]           
                elif self.rank[rootX] < self.rank[rootY]:
                    self.parent[rootX] = rootY
                    self.size[rootY] += self.size[rootX]
                else:
                    self.parent[rootY] = rootX
                    self.rank[rootX] += 1
                    self.size[rootX] += self.size[rootY]
    
    def componentsInGraph(gb):
        ds = DisjointSet()
        min_nodes = 15_001
        max_nodes = 0
    
        for x, y in gb:
            ds.union(x, y)
    
        for s in ds.size:
            if ds.parent[s] == s:
                if ds.size[s] > 1:
                    min_nodes = min(min_nodes, ds.size[s])
                    max_nodes = max(max_nodes, ds.size[s])
    
        return [min_nodes, max_nodes]