Clean Python Solution using General Union Find Class


  • 1
    U
    class Solution(object):
        def countComponents(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: int
            """
            union_find = UnionFind(n)
            for edge in edges:
                union_find.union(edge[0], edge[1])
            return filter(lambda x: x != 0, union_find.sizes).__len__()
    
    class UnionFind(object):
        
        def __init__(self, n):
            self.parents = range(n)
            self.sizes = [1] * n
        
        def find(self, x):
            if self.parents[x] == x:
                return x
            else:
                return self.find(self.parents[x])
        
        def union(self, x, y):
            
            find_x = self.find(x)
            find_y = self.find(y)
            if find_x == find_y:
                return True
            
            if self.sizes[find_x] <= self.sizes[find_y]:
                self.parents[find_x] = find_y
                self.sizes[find_y] += self.sizes[find_x]
                self.sizes[find_x] = 0
            else:
                self.parents[find_y] = find_x
                self.sizes[find_x] += self.sizes[find_y]
                self.sizes[find_y] = 0
            
            return True
            
            
            
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.