Shortest path unweighted graph
You are given an undirected graph with n nodes labeled 0..n-1 and an edge list. Each edge connects two nodes and is unweighted. Given a source node, return a list of length n where entry i is the shortest number of edges from the source to node i, or -1 if node i is unreachable. The source's own distance is 0. The graph may be disconnected and may contain multiple components; there are no self-loops and at most one edge between any pair.
Implement
bfs_distances(n: int, edges: list[list[int]], source: int) → list[int]Examples
in
[4,[[0,1],[1,2],[2,3]],0]out[0,1,2,3]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 25 min
solution.py
InputExpectedGot
[4,[[0,1],[1,2],[2,3]],0][0,1,2,3]not run yetsample