Problem
There are n cities with the numbers 0 to n - 1, and n - 1 roads between them. Each road goes in one direction only. If you ignore the directions, exactly one path connects each pair of cities.
connections[i] = [a, b] means that a road goes from city a to city b. You can change the direction of any road.
Each city must have a path to city 0 that follows the direction of each road on it. Return the smallest number of roads whose direction you must change.
Example 1
- Input:
- n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
- Output:
- 2
- Explanation:
- Change the road
1 -> 2to2 -> 1. Change the road3 -> 4to4 -> 3.
Example 2
- Input:
- n = 4, connections = [[0,1],[0,2],[0,3]]
- Output:
- 3
- Explanation:
- All three roads go away from city 0, so all three must change.
Example 3
- Input:
- n = 3, connections = [[1,0],[2,0]]
- Output:
- 0
Constraints
- 2 <= n <= 5 * 10^4
- connections.length == n - 1
- connections[i].length == 2
- 0 <= a, b <= n - 1
- a != b
SysRound wrote this statement. A reference solution checks every example.
Related questions
Continue with questions that share topics or the same question type.
Sources · 1 reference
These records explain where the question appears. A company tag or candidate report does not guarantee a future interview question.
Hello Interview · 1 record
No company association
Leetcode 1466. Reorder Routes to Make All Paths Lead to the City Zero
Reported date not specified · 0 source reports
Source snapshot: Nov 12, 2026
View source