Tunnels to Every Station
A subway system has n stations numbered 0 to n - 1. tunnels is a list of pairs [a, b] with a != b; a tunnel lets trains run both ways between stations a and b. The same pair may appear more than once.
Return a list of length n whose entry i is the fewest tunnels a train must pass through to travel from station source to station i: 0 for source itself and -1 for a station that cannot be reached at all.
Example 1
n 5
tunnels [[0,1],[1,2],[0,3]]
source 0
returns [0,1,2,1,-1]
Stations 1 and 3 are one tunnel from 0, station 2 is two tunnels away, and station 4 has no tunnel.
Example 2
n 3
tunnels [[1,2]]
source 1
returns [-1,0,1]
Station 2 is next to 1; station 0 is cut off, so its entry is -1.
Constraints
1 <= n <= 500 <= len(tunnels) <= 1000 <= a, b <= n - 1anda != b0 <= source <= n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Blocks to the Nearest ShopMedium
- Build Order ExistsMedium
- Calm SquaresMedium
- Cheapest Toll TripMedium
- Connect All OfficesMedium
- Count the Shortest RoutesMedium
- Forced SidesMedium
- Largest PatchMedium