Breath First Search Distance Given a directed graph as an adjacency list, you will determine, in this challenge, the breath first search distance of all nodes from a starting vertex, s, assuming that the weight of each edge is 1. In the example graph belove, for s=0, the distances of each vertex from s are 0 1 1 2 3 The output includes the distances for the vertices, 0, 1, 2, 3, 4, in the order of the vertex number. If s=1, then the output will be -1 0 -1 1 2 For the starting vertex 1, the vertex 0 and 2 are unreachable, so the corresponding BFS distances are -1 and -1. Input Format First line in the input contains the starting vertex s Each of the subsequent lines contains two space-separated integers, v and w, that represents an edge from the node v to w. Constraints Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1. Output Format Print the distace of each vertex from the start vertex in the order of the vertex number. Sample Input 0 0 0 1 0 2 1 3 3 4 Sample Output 0 0 1 1 2 3 Sample Input 1 1 0 1 0 2 1 3 3 4 Sample Output 1 -1 0 -1 1 2
Breath First Search Distance
Given a directed graph as an adjacency list, you will determine, in this challenge, the breath first search distance of all nodes from a starting vertex, s, assuming that the weight of each edge is 1.
In the example graph belove, for s=0, the distances of each vertex from s are
0 1 1 2 3
The output includes the distances for the vertices, 0, 1, 2, 3, 4, in the order of the vertex number.
If s=1, then the output will be
-1 0 -1 1 2
For the starting vertex 1, the vertex 0 and 2 are unreachable, so the corresponding BFS distances are -1 and -1.
Input Format
- First line in the input contains the starting vertex s
- Each of the subsequent lines contains two space-separated integers, v and w, that represents an edge from the node v to w.
Constraints
Node numbers are 0 based, i.e. if there n nodes, the nodes are numnered as 0,1,2,...,n-1.
Output Format
Print the distace of each vertex from the start vertex in the order of the vertex number.
Sample Input 0
0 0 1 0 2 1 3 3 4
Sample Output 0
0 1 1 2 3
Sample Input 1
1 0 1 0 2 1 3 3 4
Sample Output 1
-1 0 -1 1 2
Trending now
This is a popular solution!
Step by step
Solved in 2 steps