Multi-Source BFS Distances

Problem

Compute the distance from every node of an undirected unweighted graph to the nearest source.

All sources start in the queue at distance 0 and expand together. Return distances in node order, using -1 for nodes not reachable from any source. edges is a list of [u, v] pairs.

Hint

Seeding the queue with all sources gives every node its nearest-source distance.

Test cases

case 1

in: [5,[[0,1],[1,2],[2,3],[3,4]],[0,3]]

expected: [0,1,1,0,1]

case 2

in: [6,[[0,1],[2,3],[4,5]],[0,4]]

expected: [0,1,-1,-1,0,1]

case 3

in: [3,[[0,1],[1,2]],[1]]

expected: [1,0,1]

case 4

in: [2,[],[1]]

expected: [-1,0]

Starter codePython

def multi_source_bfs(n, edges, sources):
    # Your code here
    pass

4 test cases · run your code against them in the editor