The problem
Given n nodes and a list of undirected edges, decide whether they form a valid tree: everything connected and no loops.
Input: n = 5, edges 0-1, 0-2, 0-3, 1-4 Output: true
Picture it
Picture a network of computers. A tree has exactly n − 1 cables and no cable joins two computers that are already connected. We add cables one by one with union-find: any cable that links two already-connected computers makes a loop. At the end everything must be one group.
How to recognise it
- The question asks whether an undirected graph is a tree: connected, with no loops.
- A tree on n nodes has exactly n − 1 edges, which gives a cheap first test.
- Edges can be added one at a time, and a loop appears when an edge joins two nodes that are already connected.
- n up to 2,000 and 5,000 edges is small, but the check should stay linear for much larger inputs.
Start with brute force
Check the edge count, then check connectivity the long way: from every node, search the graph and confirm all n nodes are reached.
def valid_tree_brute(n, edges):
if len(edges) != n - 1:
return False
adj = defaultdict(list)
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
for s in range(n):
seen, st = {s}, [s]
while st:
x = st.pop()
for y in adj[x]:
if y not in seen:
seen.add(y)
st.append(y)
if len(seen) != n:
return False
return True
Each of n searches costs O(V + E), so time is O(V·(V + E)): about 1.4 × 10^7 for 2,000 nodes and 5,000 edges, and 10^10 for 10^5 of each. Space is O(V + E). (A single search from node 0 would already be O(V + E) and also works; the point here is that union-find answers the same question with no search at all.)
From brute force to the idea
- Find the waste. With n − 1 edges, connected and acyclic are equivalent, so you need to check only one of them. Searching from every node checks connectivity again and again.
- Count the edges first. If
len(edges) != n - 1, returnFalseat once. Too few edges cannot connect n nodes, and too many must contain a loop. - Then look only for loops. With exactly n − 1 edges, a graph with no loop must be connected. Walk the edges and keep groups with union-find.
- Detect a loop at the moment it forms. If both ends of an edge already have the same root, the edge closes a loop, so return
False. Otherwise link the roots withparent[rb] = ra. - Finish. If every edge merged two different groups, there are n − 1 merges, which leaves one group: a tree.
The key idea: n − 1 edges and no loop together imply a tree.
The key idea
A tree ⇔ exactly n − 1 edges and no union fails (no cycle).
Python solution
def valid_tree(n, edges):
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb:
return False # a loop
parent[rb] = ra # union
return True # n-1 edges, no loopIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(V·(V + E)): a full search from every node | O(V + E): adjacency lists and a seen set |
| Union-find (shown code) | O(V + E log V) at worst, close to O(V + E) in practice, because path halving keeps chains short | O(V): the parent list |
Edge cases
- One node, no edges (
n = 1,[]): returnsTrue. - Zero nodes (
n = 0): returnsFalse, because the edge count of 0 differs from −1. - A self-loop (
n = 2,[[0,0]]): the count matches, but the edge finds equal roots, so the result isFalse. - Duplicate edges (
n = 3,[[0,1],[0,1]]): returnsFalse, because the second edge closes a loop. - A loop plus an isolated node (
n = 4,[[0,1],[1,2],[2,0]]): returnsFalse. - Disconnected with the wrong count (
n = 4,[[0,1],[2,3]]): returnsFalseat the first line, because 2 ≠ 3.
Common mistakes
- Skipping the edge-count test, so a disconnected, loop-free graph such as two separate pairs is accepted.
- Testing only connectivity and ignoring loops.
- Linking nodes instead of roots (
parent[b] = a). - Using
<or>for the edge count instead of exact equality. - Forgetting that the node count n can include nodes that appear in no edge.
A forest is a graph with no loops, and it may be disconnected. Return whether the given graph is a forest. Describe what changes, then write it if you like.
Compare with our answer
Drop the edge-count test, because a forest can have fewer than n − 1 edges. The loop check stays the same.
def is_forest(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb:
return False
parent[rb] = ra
return True
is_forest(4, [[0,1],[2,3]]) is True, while valid_tree(4, [[0,1],[2,3]]) is False. Time O(V + E log V), space O(V).
A strong answer mentions: removing the exact edge-count test, keeping the loop detection, and that a forest only needs no loops, not connectivity.
1. You receive a network of 10^5 servers and cables. It is healthy only if every server can reach every other with no redundant cable. Which approach fits best?
A tree has exactly n − 1 edges and no loops, and union-find tests both in near-linear time. At most n cables allows a loop, and all-pairs searches are far too slow.
2. After the edge count equals n − 1, why is "no failed union" enough to prove the graph is connected?
Each successful union reduces the number of groups by one, so n − 1 of them take n groups down to one. Unions join groups, not single nodes, and an unused parent entry does not link anything.
3. A learner deletes the first two lines (if len(edges) != n - 1: return False). Which input now returns a wrong answer?
The two pairs contain no loop, so every union succeeds and the function returns True, though the graph is disconnected. In the other inputs the loop test alone gives the right answer.
Score 60% or more and the lesson is marked complete.