Graph Valid Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given n nodes (0 to n-1) and a list of undirected edges, is the graph a valid tree: connected and with no cycle?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many edges must a tree with n nodes have?
- Hint 2With the right number of edges, no cycle is the same as connected. How do you detect a cycle as you add edges?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Villages and roads. Every village starts as its own group with itself as head. Building a road merges the two villages' groups under one head. If you are about to build a road between two villages that already share the same head, they were already connected: this road would create a loop. A proper tree of n villages needs exactly n - 1 roads, so any other count fails immediately.
- The obvious way
DFS from node 0 checking visited counts and cycles: also O(n + edges), just longer to write.
- The key insight
If edges != n - 1, return False. Give each node its own head. For each edge find the heads of both ends (following heads up to the top, shortening the path as you go); if the heads are equal this edge closes a loop: False. Otherwise make one head point to the other. If every edge merged two different groups, it is a tree.
- The algorithm
- Wrong number of edges (not n - 1)? False.
- head[v] = v for every node.
- For each edge: find both heads.
- Same head: False. Else join the groups. All edges done: True.
Watch it run
Examplen = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
4 edges for 5 nodes: n - 1, so the count is right. Every village is its own group.
groups: 5
Where people slip
- Check the edge count first; n - 1 edges and no cycle together imply connected.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def valid_tree(n, edges):
if len(edges) != n - 1:
return False # a tree has exactly n - 1 edges
head = list(range(n)) # every village is its own head
def find(village):
while head[village] != village:
head[village] = head[head[village]] # shorten the path as we climb
village = head[village]
return village
for first, second in edges:
first_head, second_head = find(first), find(second)
if first_head == second_head:
return False # already connected: this road makes a loop
head[first_head] = second_head # merge the two groups
return TrueNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.