Concise Python Union-Find with Minimum Depth


  • 0
    Z
    def getParent(tree,i):
        d = 0 # depth
        while tree[i] != -1:
            i = tree[i]
            d += 1
        return i,d
    
    def countComponents(n, edges):
        tree = [-1] * n
        for ed in edges:
            n0, n1 = ed[0],ed[1]
            (p0,d0) = getParent(tree,n0)
            (p1,d1) = getParent(tree,n1)
            if p0 != p1:
                if d0 < d1:
                    tree[p0] = p1
                else:
                    tree[p1] = p0
        return sum(1 for n in tree if n == -1)

Log in to reply
 

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