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
Reorder routes to make all paths lead to city zero counts the minimum edge reversals so every city can reach city 0. The roads form a tree — n cities and n − 1 edges, connected — so exactly one path exists between any two cities.
That tree structure is what makes the problem tractable. There is no choice of route, so each edge either already points the right way or must be flipped:
- Traverse outward from city 0; an edge pointing away from 0 must be reversed, and an edge pointing back toward 0 is already correct.
The traversal direction and the counting direction are opposites, which is the part worth getting straight. Moving away from 0, an edge oriented in the same direction as the traversal points away from 0 and needs flipping.
The implementation trick is to build the graph with both directions present, tagging each entry with whether it is an original edge or an added reverse one. The traversal can then move freely, while the tag records which orientations cost a reversal.
Storing a cost of 1 on original edges and 0 on the synthetic reverses turns the answer into a simple sum along the traversal.
Building only the original directions makes the graph unreachable — the traversal cannot cross an edge pointing the wrong way, and most cities are never visited.
A visited set is still required despite the tree structure, because the doubled edges create two-cycles that would otherwise loop forever.
Each node and edge is processed once, giving O(n) time and O(n) space.
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).
Use the tree structure
With n cities and n - 1 connected edges, exactly one path exists between any two cities — there is no routing choice, only orientation.
Build both directions
Add each edge forwards and backwards, tagging which is original. Building only original directions leaves the graph untraversable.
Tag reversal cost
Give original edges a cost of 1 and synthetic reverses a cost of 0. The answer becomes a sum along the traversal.
Traverse outward from zero
Start at city 0 and move outward. An edge oriented along the traversal points away from 0 and must be reversed.
Mind the direction logic
The traversal direction and the counting direction are opposites. Moving away from 0, same-direction edges are the ones that cost a flip.
Keep a visited set
The doubled edges create two-cycles, so a visited set is required despite the tree structure, or the traversal loops between adjacent nodes.
Cost of the traversal
Each node and edge is processed once, giving O(n) time and O(n) space for the adjacency list and visited set.
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.