Reorder Routes to Make All Paths Lead to the City Zero
01 · Problem
A country has n cities numbered 0 to n - 1, linked by exactly n - 1 one-way roads. If you ignore the directions, the roads form a tree, so there is exactly one route between any two cities. Each connections[i] = [a, b] is a road that can only be driven from city a to city b.
City 0 is hosting a big event and everyone must be able to drive there. You may reverse the direction of any road. Return the minimum number of roads you must reverse so that every city can reach city 0.
It is guaranteed that a valid reorientation always exists (the underlying undirected graph is connected).
02 · Examples
n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
2
Roads 1->0 and 3->2 already point toward city 0. Road 1->2 points away from 0 and must become 2->1, and road 3->4 must become 4->3. That is 2 reversals.
n = 3, connections = [[1,0],[2,0]]
0
Both roads already lead into city 0, so nothing needs to change.
n = 4, connections = [[0,1],[1,2],[2,3]]
3
Every road on the chain points away from city 0, so all 3 must be reversed.
03 · Constraints
- 012 <= n <= 5 * 104
- 02connections.length == n - 1
- 03connections[i].length == 2
- 040 <= a, b <= n - 1 and a != b
- 05Ignoring direction, the roads form a tree
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.