Show problems as
Classic problem #1466MediumDepth-First SearchBreadth-First SearchGraph Theory

Reorder Routes to Make All Paths Lead to the City Zero

Real-world version: Roads to Turn Round for the Depot
Tracked in this browser only
Read Reorder Routes to Make All Paths Lead to the City Zero on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A region has n towns numbered from zero, joined by n - 1 one-way roads listed in connections, each [from, to]. Ignoring the directions, the roads join every town to every other with no loops.

Return the fewest roads that must be turned round so that every town can reach town 0 by following the roads the way they point.

Examples

Example 1

Input
n = 6, connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
Output
3

Sweeping outwards from town 0, the roads to 1, to 3 and to 5 all point away from it and must be turned; the roads from 2 and from 4 already point the right way.

Example 2

Input
n = 4, connections = [[3, 2], [2, 1], [1, 0]]
Output
0

The towns run in a line and every road already points towards town 0.

Example 3

Input
n = 4, connections = [[0, 1], [1, 2], [2, 3]]
Output
3

The towns run in a line and every road points away from town 0, so all three must be turned.

Constraints

  • 2 <= n <= 5 * 10^4
  • connections.length == n - 1
  • connections[i].length == 2
  • 0 <= connections[i][0] <= n - 1
  • 0 <= connections[i][1] <= n - 1
  • The two towns on a road are different
  • Ignoring directions, the roads join every town with no loops

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_reorder(n: int, connections: list[list[int]]) -> int:
Java
public int minReorder(int n, int[][] connections)

More on the same topics