Point Every Road Home
MediumGraphs
Problem
A festival site has n zones numbered 0 to n - 1, connected by n - 1 one-way paths. Each [a, b] in paths lets people walk from a to b only. Ignoring direction, the paths form a tree.
For the evacuation plan, everyone must be able to walk to the main gate at zone 0. Return the minimum number of paths whose direction must be reversed.
Example 1
- Input:
- n = 5, paths = [[0,1],[2,1],[3,2],[3,4]]
- Output:
- 2
The zones form the line 0 – 1 – 2 – 3 – 4. Paths 0→1 and 3→4 point away from the gate and must be flipped.
Example 2
- Input:
- n = 3, paths = [[1,0],[2,0]]
- Output:
- 0
Both paths already lead to the gate.
Constraints
- 2 ≤ n ≤ 5 · 10^4
- paths.length = n - 1
- Ignoring direction, the paths form a tree.
Hint
Show the first hint
In a tree, every path has exactly one correct direction: toward zone 0. Which one is that?
Walkthrough
How to approach it
01Clarify before coding
- Is the undirected shape always a tree? Yes, so each zone has a unique route to 0.
- Does reversing cost the same for every path? Yes, 1 each.
- Can the answer be 0? Yes, when every path already leads toward 0.
02Brute force
For every zone, trace its unique route to 0 and count the edges pointing the wrong way, deduplicating edges with a set.
Cost: O(n²) for routes in a long chain, and the deduplication is error-prone.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.