Reachable after a closure: hints, no solution
Medium · Graphs
A transit network has n stations numbered from 0 to n - 1, and each row of links is a two-way connection between two different stations. Riders start at the hub station and can move along links from station to station.
Today the station called closed is shut, so nobody can enter, leave or pass through it. Return how many stations riders starting at the hub can still reach, counting the hub itself. The closed station never counts. If the hub is the closed station, return 0.
Examples
- Input
- n = 6, links = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], hub = 0, closed = 1
- Output
- 1
- Note
- Station 1 is the only way out of the hub, so riders are stuck at the hub alone.
- Input
- n = 6, links = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], hub = 0, closed = 3
- Output
- 5
- Note
- With station 3 closed, stations 0, 1, 2, 4 and 5 are all still reachable.
- Input
- n = 6, links = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], hub = 2, closed = 2
- Output
- 0
- Note
- The hub itself is closed, so nobody can start.
Constraints
- 1 <= n <= 90000
- 0 <= links.length <= 90000
- Links join two different stations; a pair may repeat
- 0 <= hub, closed < n
Hint 1: a nudge
If the shut station did not exist at all, which stations would riders from the hub still be able to walk to? Is there a case where the answer is known immediately?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.