All Roads Lead to the Hub

Medium

A region has towns towns numbered from 0 to towns - 1 and towns - 1 narrow roads. Ignoring direction, there is exactly one route between any two towns (the road network is a tree). Every road is one-way: roads[i] = [a, b] means you can only drive along it from town a to town b. A big fair is coming to the hub, town 0, and it must be possible to drive to the hub from every town. To achieve that, some roads may be turned to point the other way. Return the smallest number of roads that have to be turned.

Example 1

towns=5, roads=[[0, 2], [2, 1], [3, 2], [4, 0]] → 2

Roads 0 → 2 and 2 → 1 lead away from the hub and must be turned. Roads 3 → 2 and 4 → 0 already lead towards it. The answer is 2.

Example 2

towns=4, roads=[[1, 0], [2, 1], [3, 1]] → 0

Every town can already reach town 0, so nothing has to be turned.

Example 3

towns=2, roads=[[0, 1]] → 1

Constraints

2 ≤ towns ≤ 5 · 10⁴
len(roads) == towns - 1
roads[i] = [a, b], 0 ≤ a, b ≤ towns - 1, a ≠ b
Ignoring direction, the roads connect all towns

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

towns=5, roads=[[0, 2], [2, 1], [3, 2], [4, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 59 tests on the server, hidden ones included.