My python union-find solution


  • 0
    V
    class UnionFind:
        def __init__(self, n):
            self.count = n
            self.father = {}
            for i in range(n):
                self.father[i] = i
        
        def compressed_find(self, x):
            parent = self.father.get(x)
            while parent != self.father.get(parent):
                parent = self.father.get(parent)
            
            temp = -1
            fa = self.father.get(x)
            while fa != self.father.get(fa):
                temp = self.father.get(fa)
                self.father[fa] = parent
                fa = temp
            
            return parent
        
        def union(self, x, y):
            fa_x = self.compressed_find(x)
            fa_y = self.compressed_find(y)
            if fa_x != fa_y:
                self.father[fa_x] = fa_y
                self.count -= 1
                return True
            else:
                return False
            
            
    class Solution(object):
        def validTree(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: bool
            """
            
            if edges == None:
                return False
            
            uf = UnionFind(n)
            
            for e in edges:
                flag = uf.union(e[0], e[1])
                if flag == False:
                    return False
            
            return uf.count == 1
    

    Union all edges, if two nodes have been connected, a.k.a. have the same parent: return False.

    Count # of unions, return True only if count=1, since a tree contains the only one union.


Log in to reply
 

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