Core Insight A visited structure makes each vertex’s work happen at most once.
Common Pitfall Mark a node visited when it is scheduled, not after duplicate work is queued.
Description
Check if a graph is a valid tree.
Constraints
- Time Complexity:
O(V+E) - Space Complexity:
O(V+E)
Tags
dfsbfsunion-findgraph
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a start node or component.
- Add it to the traversal frontier.
- Visit valid unseen neighbors.
- Repeat for every remaining component if needed.
def validTree(n, edges):
if not n:
return True
adj = {i: [] for i in range(n)}
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
visit = set()
def dfs(i, prev):
if i in visit:
return False
visit.add(i)
for j in adj[i]:
if j == prev:
continue
if not dfs(j, i):
return False
return True
return dfs(0, -1) and n == len(visit)