Python Union Find


  • 0
    R
    def countComponents(self, n, edges):
        roots = range(n)
        groups = {i:{i} for i in roots}
        
        for n1, n2 in edges:
            r1, r2 = roots[n1], roots[n2]
            if r1 == r2:
                continue
            l1 = len(groups.get(r1, []))
            l2 = len(groups.get(r2, []))
            if l1 < l2:
                r1, r2 = r2, r1
            groups[r1] |= groups[r2]
            for i in groups.pop(r2, []):
                roots[i] = r1
    
        return len(groups)
    

Log in to reply
 

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