Reorder Routes to Make All Paths Lead to City Zero
Medium · Graphs · Depth-First Search · Breadth-First Search · Graph
Problem
There are n cities numbered 0 to n - 1 and exactly n - 1 roads, arranged so that there is exactly one route between any two cities if direction is ignored (a tree). Every road is one-way: connections[i] = [a, b] is a road from a to b.
The capital, city 0, is hosting an event and everyone must be able to drive there. Return the minimum number of roads whose direction you must reverse so that every city can reach city 0.
Examples
Input: n = 5, connections = [[0,1],[1,2],[3,1],[4,0]] Output: 2
Roads 0 -> 1 and 1 -> 2 point away from the capital and are reversed; 3 -> 1 and 4 -> 0 already lead toward it.
Input: n = 3, connections = [[1,0],[2,0]] Output: 0
Both roads already lead to 0.
Input: n = 2, connections = [[0,1]] Output: 1
The single road must be reversed.
Constraints
- 2 <= n <= 5 · 10^4
- len(connections) == n - 1
- connections[i] == [a, b] with 0 <= a, b < n and a != b
- The roads form a tree when direction is ignored
Approaches
- Baseline: grow the reached set by sweeping the roads — time O(n²), space O(n)
Follow-up
The answer is fixed by the tree: exactly the roads pointing away from 0 are reversed, so no search over choices is needed. The use cases let you pick the capital (move it across one road at a time) and drop the tree shape (a 0-1 shortest path).
Related problems
Start free on Cariara · Coding problems · System design studio
