Python Disjoint Set


  • 0
    class Solution(object):
        def validTree(self, n, edges):
            f = [ i for i in xrange(n) ]
            def union(a, b):
                fa, fb = find(a), find(b)
                f[fa] = fb
            def find(a):
                if a == f[a]:
                    return a
                else:
                    f[a] = find(f[a])
                    return f[a]
            for edge in edges:
                e1, e2 = edge[0], edge[1]
                f1, f2 = find(e1), find(e2)
                if f1 == f2:
                    return False
                union(f1, f2)
            for i in xrange(1, n):
                if find(i) != find(0):
                    return False
            return True
    

Log in to reply
 

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