Skip to main content

Graph Valid Tree


Given a directed graph, determine if it is a valid tree (contains no cycles and is connected).

Example 1
Input: n = 5, edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true


all//Graph Valid

def valid_tree(n, edges):
# Create an adjacency list representation of the graph
graph = [[] for _ in range(n)]
for v, w in edges:

# Perform a BFS to ensure the graph is connected
visited = [False] * n
queue = [0]
while queue:
v = queue.pop(0)
visited[v] = True
for w in graph[v]:
if visited[w] == False:

# Check if all nodes have been visited
if all(visited):
# Check if the graph has any cycles
edges_remaining = len(edges)
for v in range(n):
edges_remaining -= len(graph[v])

if edges_remaining == 0:
return True
return False