Fewest Hops From One Town to Every Other
Implement stepsFromSource
You are given a network of towns connected by two-way roads as an adjacency list, and a starting town. Every road counts as one hop. For every town, find the fewest hops needed to get there from the starting town, or -1 if it cannot be reached.
Because all roads cost the same, a breadth-first search discovers each town by its shortest route the first time it reaches it.
Example 1:
Input: graph = [[1,2],[0,3],[0,3],[1,2,4],[3],[6],[5],[]], src = 1
Output: [1,0,2,1,2,-1,-1,-1]
Example 2:
Input: graph = [[1],[0,2],[1]], src = 2
Output: [2,1,0]
Example 3:
Input: graph = [[]], src = 0
Output: [0]
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 10 towns numbered 0 … n-1; graph[u] lists, in increasing order, every town directly linked to u by a road (adjacency-list form of an undirected graph) - ●
If v is in graph[u] then u is in graph[v]; every road counts as exactly one hop - ●
0 ≤ src < n is the starting town - ●
Return an array where entry i is the fewest hops from src to town i, or -1 if town i cannot be reached
graph =
[[1,2], [0,3], [0,3], [1,2,4], [3], [6], [5], []]
src =
1