Graph Valid Tree

Problem: Graph Valid Tree

We can do depth-first search at random node in the graph and mark searched node as visited. If we come back to a visited node, there's a cycle in the graph. If not all nodes are visited, then there are isolated nodes.

Code in Python:

from collections import defaultdict

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        visited = [False] * n
        adj = defaultdict(list)

        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        stack = [0]
        while stack:
            u = stack[-1]
            visited[u] = True
            for v in adj[u]:
                if visited[v]: return False
                adj[u].remove(v)
                adj[v].remove(u)
                stack.append(v)
                break
            if stack[-1] == u: stack.pop()

        for x in visited:
            if not x: return False

        return True