All roads lead to the capital
Count the one-way roads that point the wrong way by walking out from the capital across a tree. About 12 minutes.
Keep the direction as a flag
A country has n cities joined by n - 1 one-way roads, so that ignoring direction every city can reach every other. The capital is city 0. You want everyone to be able to drive to the capital, by reversing as few roads as possible.
In a tree there is exactly one route between two cities, so every road is either already pointing toward the capital or not. Walk outwards from the capital, treating roads as two-way, but remember each road's real direction. A road crossed in its stored direction points away from the capital, so it needs flipping.
adj[a].append((b, 1)) # 1: points away adj[b].append((a, 0)) # 0: points back
- flips
- 0
Start at the capital, city 0.
You walk from the capital across a road stored as 'from the capital's side to the far side'. What does that tell you?
- AIt points away from the capital, so it must be reversed
- BIt already points toward the capital
- CDirection doesn't matter in a tree
Show the answer
It points away from the capital, so it must be reversed. Cars on the far side would have no way to come back along it.
Reroute to the capital
There are n cities numbered 0 to n − 1, and n − 1 one-way roads. roads[i] = [a, b] is a road you can drive from city a to city b. If you ignored the directions, every city could reach every other, with exactly one route between any two. City 0 is the capital. Return the fewest roads that must be reversed so that every city can drive to the capital.
n = 5, roads = [[0, 1], [2, 1], [1, 3], [4, 0]] → 2
2 ≤ n ≤ 100,000