Reorder Routes to Make All Paths Lead to City Zero
Reorder Routes to Make All Paths Lead to City Zero: n cities form a tree with directed roads. Return the minimum number of roads that must be reversed so every city can reach city 0.
- 2 <= n <= 5 * 10⁴
- connections.length == n - 1
- connections[i].length == 2
- 0 <= connections[i][0], connections[i][1] <= n - 1
Intuition
The roads form a tree, so there is exactly one route between any two cities — no choices to make. Walk outward from city 0 ignoring direction, and count the edges that point away from 0: each one must be flipped so traffic can flow back toward the capital.
When a graph is a tree, uniqueness of paths removes all choice and turns an optimisation into a counting problem. The tell here is connections.length == n - 1 with full connectivity. Tagging synthetic reverse edges so the traversal can move freely while still remembering orientation is the reusable trick.
Approach
Before reading on: the roads form a tree, so how many routes exist from any city to city 0? Given that, when you step outward from 0 along an edge, what does its original direction tell you? Aim for O(n).
Traverse ignoring direction, but remember it
Since the underlying structure is a tree, walking from city 0 reaches every city exactly once by a unique route. To move freely you must build the adjacency list with both directions — but the original orientation still matters, so tag each entry: store the real road as (neighbour, 1) and the synthetic reverse as (neighbour, 0). The flag records whether traversing that way follows the road or goes against it.
Count the edges pointing away from zero
Every city must reach city 0, so along the unique path from any city back to 0 all roads must point inward. As the traversal moves outward from 0 to a neighbour, an edge tagged 1 points outward — the wrong way — and must be reversed, so add one to the answer. An edge tagged 0 already points back toward 0 and costs nothing. Summing those flags over the whole traversal gives the minimum directly.
Why this is optimal, not just correct
In a tree the route from each city to 0 is forced, so every edge on it must point the right way — there is no alternative path that could avoid a reversal. Each edge is therefore either necessarily flipped or necessarily left alone, and the count of the first group is a lower bound as well as an achievable answer. Cost is O(n) time and space, since a tree on n nodes has exactly n−1 edges.
Solution & live demo
Common pitfalls
Building a one-directional adjacency list
graph[a].append((b, 1))
graph[a].append((b, 1)) graph[b].append((a, 0))
Following only the real directions, the traversal cannot leave city 0 if all roads point outward — or reaches almost nothing. Both directions are needed to move, with a flag to remember which is genuine.
Counting reversals in the wrong direction
reversals += 1 - is_forward
reversals += is_forward
Moving outward from 0 along a real road means that road points away from the capital, so it is the one needing a flip. Counting the synthetic edges instead gives exactly the complement.
Forgetting the visited check
stack.append(neighbour)
if not visited[neighbour]:
visited[neighbour] = True
stack.append(neighbour)Because every edge is stored twice, the traversal walks straight back to the city it came from and loops forever, double-counting edges on the way.
Edge cases
Every traversal step follows a reverse edge, so the answer is 0.
Every edge must be flipped, giving n−1.
A single road, reversed only if it points away from 0.
Each spoke is judged independently by its own direction.
The traversal follows it to the end; an explicit stack avoids recursion limits when n is large.