627. Reorder Routes to Make All Paths Lead to the City Zero
A country has n cities numbered 0 to n − 1, linked by n − 1 one-way roads. If you ignore the directions, the road network forms a tree: there is exactly one route between any two cities. The capital is city 0, and every citizen needs to be able to drive to it — but some roads currently point the wrong way.
Your function receives the integer n and the list connections, where connections[i] = [a, b] means there is a road currently directed from city a to city b. You may reverse the direction of any road. Return the minimum number of roads that must be reversed so that every city can reach city 0, as an integer.
A solution always exists because the underlying network is connected.
Example 1:
Input: n = 6, connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
Output: 3
Explanation: Reverse 0→1, 1→3, and 4→5 — each points away from the capital's side of its road. The roads 2→3 and 4→0 already carry traffic toward city 0 and stay as they are.
Example 2:
Input: n = 5, connections = [[1, 0], [1, 2], [3, 2], [3, 4]]
Output: 2
Explanation: Reverse 1→2 and 3→4. After that, city 4 drives 4→3→2→1→0 and every other city has a directed route to 0 as well.
Example 3:
Input: n = 3, connections = [[1, 0], [2, 0]]
Output: 0
Explanation: Both roads already point at the capital; nothing to do.
Constraints:
- 2 ≤ n ≤ 5 * 10⁴
- connections.length == n - 1
- connections[i].length == 2
- 0 ≤ a, b ≤ n - 1
- a ≠ b
Hints:
Ignoring directions, the network is a tree rooted at city 0 — each road links a parent to a child, and every city's only way home runs through its parent.
So each road's correct orientation is forced: it must point from the child (farther from 0) toward the parent. A road needs a flip exactly when it points away from city 0.
Store each road twice in an adjacency list — the real direction with cost 1, the reverse with cost 0 — then walk the tree outward from 0 and sum the costs of the edges you traverse.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 6, connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
Expected output: 3