Reorder Routes to Make All Paths Lead to City Zero
Explanation & Solution
Description
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network forms a tree). Last year, the ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [a_i, b_i] represents a road from city a_i to city b_i.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task is to reorient some roads such that each city can reach city 0. Return the minimum number of edges that need to be reversed.
It is guaranteed that each city can reach city 0 after reordering.
Examples
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: We need to reverse the roads [0,1], [1,3], and [4,5] so that every city can reach city 0.
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: We need to reverse the roads [1,2] and [3,4] so that every city can reach city 0.
Input: n = 3, connections = [[1,0],[2,0]]
Output: 0
Explanation: All roads already point toward city 0, so no reversals are needed.
Constraints
- 2 <= n <= 5 * 10^4
- connections.length == n - 1
- connections[i].length == 2
- 0 <= a_i, b_i <= n - 1
- a_i != b_i
Approach
Graphs pattern
1. Build an Undirected Adjacency List with Direction Tracking
- For each directed edge [a, b], add b to a's neighbor list marked as an original edge.
- Also add a to b's neighbor list marked as a reverse edge.
- This lets us traverse the tree in both directions while knowing which edges point which way.
2. BFS from City 0
- Start a BFS (or DFS) from city 0, visiting all cities.
- Use a visited array to avoid revisiting nodes.
3. Count Edges Pointing Away from City 0
- As we traverse from city 0 outward, any original edge we follow means the road points away from 0.
- An edge pointing away from 0 must be reversed so that the destination city can reach 0.
- Increment the count for each such edge.
4. Return the Count
- The total count is the minimum number of reversals needed.
Key Insight
- Since the cities form a tree (n cities, n-1 edges, all connected), there is exactly one path between any two cities.
- By doing BFS from city 0, we discover the tree layer by layer. Any original edge that points from parent to child (away from 0) needs reversal, because we need the child to be able to reach 0 through its parent.
- Reverse edges (child to parent) are already oriented correctly and cost nothing.
Visualization
Press play to start bfs path counting