261. Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

 def validTree1(n: int, edges: List[List[int]]):

   

        visited = set()

        def hasCycle(node, cameFrom):

           

            if node in visited:

                return True                

            visited.add(node)

                   

            for nei in edgeMap[node]:

                if nei != cameFrom:                    

                    detected = hasCycle(nei, node)

                    if detected:

                        return True

                   

            return False

       

        edgeMap = {}

        for i in range(n):

            edgeMap[i] = []

        for e in edges:

            edgeMap[e[0]].append(e[1])

            edgeMap[e[1]].append(e[0])

       

        return not hasCycle(0, -1) and len(visited) == n

   

def validTree(n: int, edges: List[List[int]]):

    if len(edges) != n - 1:

        return False

           

    visited = set()

   

    def dfs(node):

        if node in visited:

            return

        visited.add(node)

       

        for neighbour in edgeMap[node]:

            dfs(neighbour)

    edgeMap = {}

    for i in range(n):

        edgeMap[i] = []

    for e in edges:

        edgeMap[e[0]].append(e[1])

        edgeMap[e[1]].append(e[0])

       

    dfs(0)

    return len(visited) == n