Easy-understanding python union/find with compression and weighting

  • 0

    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:
            if r not in u.parent:
            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: 
        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

    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.