Python Graph + BFS


  • 0
    class Solution(object):
        def validTree(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: bool
            """
            # equivalent to the circle detection problem
            
            graph = {i: set() for i in xrange(n)}
            
            for v1, v2 in edges:
                graph[v1].add(v2)
                graph[v2].add(v1)
            
            seen = set()
            visited = set()
            
            def bfs(node):
                queue = [node]
                for v in queue:
                    for nei in graph[v]:
                        if nei in visited:
                            continue
                        if nei in seen:
                            return False
                        if nei not in seen:
                            seen.add(nei)
                            queue.append(nei)
                    visited.add(v)
                return True if len(queue) == n else False
            
            return bfs(0)
    

Log in to reply
 

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