Simple Python DFS Implementation


  • 0
    M
        def validTree(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: bool
            """
            from collections import defaultdict, deque
            
            G = { num: set() for num in xrange(n) }
            for edge in edges:
                u, v = edge
                G[u].add(v)
                G[v].add(u)
            
            S = [0]
            visited = set()
            while S:
                num = S.pop()
                if num in visited:
                    return False
                visited.add(num)
                S.extend(G[num] - visited)
    
            return len(visited) == len(G)
    

Log in to reply
 

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