261. Graph vaild tree

solve.py

from collections import defaultdict

def solve(n, edges):

    def has_cycle(node, parent, adj, visited):
        visited.add(node)

        for n in adj[node]:
            # node has been visited and not the parent
            if n in visited and n != parent:
                return True

            # process neighbor, dont visit parent
            if n not in visited and has_cycle(n, node, adj, visited):
                return True
        return False

    # create adj list
    adj = defaultdict(list)
    for edge in edges:
        x, y = edge
        adj[x].append(y)
        adj[y].append(x)

    # better approach, check for cycles
    # and it is a tree if, every node has been visited
    visited = set()
    if has_cycle(0, -1, adj, visited):
        return False

    return len(visited) == n

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
# edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
print(solve(n, edges))