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...

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 froms 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.

Ifs=1, then the output will be

-1 0 -1 1 2

For the starting vertex1, the vertex0 and2 are unreachable, so the corresponding BFS distances are -1 and -1.

Input Format

• First line in the input contains the starting vertexs
  


• Each of the subsequent lines contains two space-separated integers,v andw, that represents an edge from the nodev tow.

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

" + adjList.get (v)); 15 16 17 18 public void add (Integer vertex) { if (adjList.containskey (vertex)) 19 20 return; 21 adjList.put(vertex, new Arraylist()); } 22 23 public void add (Integer source, Integer dest) { add (source); add (dest); adjList.get (source).add (dest); 24 25 26 28 29 30 /* Indegree of each vertex as a Map */ public Map inDegree () { Map result = new HashMap (); for (Integer v : adjlist.keySet ()) result.put(v, 0); for (Integer from : adjList.keySet ()) { for (Integer to : adjlist.get(from)) { 31 32 33 34 35 36 37 result.put (to, result.get(to) + 1); 38 39 40 return result; 41 42 43 public Map outDegree () { Map result = new HashMap (); for (Integer v : adjList.keySet()) result.put (v, adjList.get(v).size()); return result; 44 45 46 47 48 49 50 } 3. N34 n67 00 o 123 456 00 9 o 123mtn6 N 00 O o. IN2 233 m3m m3nmmo "/>
Extracted text: (1) (4 (2 1 vimport java.io.*; 2 import java.util.*; 3 import java.util.stream.Collectors; 4 5 vpublic class Solution { public static class DirectedGraph { /* Adjacency List representation of the given graph */ private Map> adjList = new HashMap> (); 10 public String tostring() { StringBuffer s = new StringBuffer (); for (Integer v : adjlist.keySet()) s. append ("\n return s.toString (); } 11 13 14 " + v + " -> " + adjList.get (v)); 15 16 17 18 public void add (Integer vertex) { if (adjList.containskey (vertex)) 19 20 return; 21 adjList.put(vertex, new Arraylist()); } 22 23 public void add (Integer source, Integer dest) { add (source); add (dest); adjList.get (source).add (dest); 24 25 26 28 29 30 /* Indegree of each vertex as a Map */ public Map inDegree () { Map result = new HashMap (); for (Integer v : adjlist.keySet ()) result.put(v, 0); for (Integer from : adjList.keySet ()) { for (Integer to : adjlist.get(from)) { 31 32 33 34 35 36 37 result.put (to, result.get(to) + 1); 38 39 40 return result; 41 42 43 public Map outDegree () { Map result = new HashMap (); for (Integer v : adjList.keySet()) result.put (v, adjList.get(v).size()); return result; 44 45 46 47 48 49 50 } 3. N34 n67 00 o 123 456 00 9 o 123mtn6 N 00 O o. IN2 233 m3m m3nmmo

bfsd = bfsDistance (digraph, sVertex); String s = bfsd.entrySet().stream ().map (e -> String.value0f(e.getValue())).collect(Collectors.joining(" ")); bufferedwriter.write(s); 75 76 77 78 79 bufferedReader.close(); 80 bufferedwriter.close(); 81 } 82 } 83 "/>
Extracted text: 49 50 51 52 53 // Complete the bfsDistance function below. public static Map bfsDistance (DirectedGraph digraph, Integer start) { Map distance = new HashMap (); 54 55 56 return distance; } 57 58 59 public static void main(String[] args) throws I0Exception { 60 Bufferedwriter bufferedwriter = new Bufferedwriter (new Filewriter (System.getenv ("OUTPUT_PATH"))); 61 62 63 BufferedReader bufferedReader = new BufferedReader (new InputStreamReader (System.in)); 64 65 int svertex = Integer.parseInt (bufferedReader.readLine ().trim ()); 66 67 DirectedGraph digraph = new DirectedGraph(); 68 69 String line; while ((line = bufferedReader.readline ()) != null) { String[] v = line.split(" "); digraph.add (Integer.parseInt(v[0]), Integer.parseInt (v[1])); 70 71 72 73 74 Map bfsd = bfsDistance (digraph, sVertex); String s = bfsd.entrySet().stream ().map (e -> String.value0f(e.getValue())).collect(Collectors.joining(" ")); bufferedwriter.write(s); 75 76 77 78 79 bufferedReader.close(); 80 bufferedwriter.close(); 81 } 82 } 83