Easy-understanding python union/find with compression and weighting


  • 0
    S

    class Solution(object):

    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        u = Union()
        for l, r in edges:
            if l not in u.parent:
                u.add(l)
            if r not in u.parent:
                u.add(r)
            u.unite(l, r)
        return u.count + n - len(u.parent)
    

    class Union:

    def __init__(self):
        self.parent = {}
        self.weight = {}
        self.count = 0
        
    def add(self, x):
        self.parent[x] = x
        self.weight[x] = 1
        self.count += 1
        
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        px = self.find(x) 
        py = self.find(y)
        if px == py: 
            return 
        if self.weight[px] > self.weight[py]:
            px,py = py,px
        self.parent[px] = py
        self.weight[py] += self.weight[px]
        self.count -= 1

  • 0
    Z

    Why use dictionary to store parent- child pair? Isn't this too expensive?


Log in to reply
 

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