Show problems as
Classic problem #2858HardDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph Theory

Minimum Edge Reversals So Every Node Is Reachable

Real-world version: Retooling the One-Way Corridors
Tracked in this browser only
Read Minimum Edge Reversals So Every Node Is Reachable on LeetCode(opens in a new tab)

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

A depot holds bays storage bays numbered 0 through bays - 1, joined by bays - 1 one-way corridors. Each entry corridors[i] = [a, b] is a corridor that a cart may drive only from bay a to bay b. Ignore the arrows and the layout is a tree: exactly one route of corridors joins any two bays.

Maintenance can retool a corridor so it runs only the other way, and each retooling is one work order.

For every bay s, report the fewest work orders that let a cart parked at bay s drive to every bay in the depot. Each bay is costed on its own: the corridors always start out as given, so a retooling planned for one bay does not carry over to the next.

Return an array of length bays whose entry s holds that count for bay s.

Examples

Example 1

Input
bays = 4, corridors = [[0, 1], [1, 2], [3, 2]]
Output
[1, 2, 3, 2]

From bay 0 a cart drives to bay 1 and bay 2 as the corridors stand, and one work order on the corridor between bay 3 and bay 2 lets it finish at bay 3. From bay 3 the cart drives straight to bay 2, then needs the corridor into bay 1 and the corridor into bay 0 retooled, which is two work orders.

Example 2

Input
bays = 4, corridors = [[1, 0], [2, 0], [3, 0]]
Output
[3, 2, 2, 2]

All three corridors run into bay 0, so a cart starting there needs all three retooled. A cart starting at bay 1 drives into bay 0 as things stand and needs the other two retooled.

Example 3

Input
bays = 2, corridors = [[1, 0]]
Output
[1, 0]

A cart at bay 1 already drives to bay 0, and a cart at bay 0 needs that single corridor retooled.

Constraints

  • 2 <= bays <= 10^5
  • corridors.length == bays - 1
  • corridors[i].length == 2
  • 0 <= corridors[i][0] < bays
  • 0 <= corridors[i][1] < bays
  • corridors[i][0] != corridors[i][1]
  • Read without their arrows, the corridors form a tree over the bays

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 corridor_flips(bays: int, corridors: list[list[int]]) -> list[int]:
Java
public int[] corridorFlips(int bays, int[][] corridors)

More on the same topics