FunctionRacerProblemsRace

Tunnels to Every Station

EasyGraphsPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems