package hackerrank;

import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/bfsshortreach
 */
public class BreadthFirstSearchShortestReach {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // TODO
    }
}

@@ -35,233 +35,2139 @@
 til.
-Scanner;%0A%0A/**%0A * https://www.hackerrank.com/challenges/bfsshortreach%0A */%0Apublic class BreadthFirstSearchShortestReach %7B%0A    public static void main(String%5B%5D args) %7B%0A        Scanner in = new Scanner(System.in);%0A        // TODO
+HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.LinkedList;%0Aimport java.util.Map;%0Aimport java.util.Queue;%0Aimport java.util.Scanner;%0Aimport java.util.Set;%0A%0A/**%0A * https://www.hackerrank.com/challenges/bfsshortreach%0A */%0Apublic class BreadthFirstSearchShortestReach %7B%0A    private static void bfs(int source, int vertices, Map%3CInteger, Set%3CInteger%3E%3E adjList) %7B%0A        Map%3CInteger, Integer%3E paths = new HashMap%3C%3E();%0A        Set%3CInteger%3E marked = new HashSet%3C%3E();%0A        marked.add(source);%0A        Queue%3CInteger%3E queue = new LinkedList%3C%3E();%0A        queue.add(source);%0A        while (!queue.isEmpty()) %7B%0A            int vertex = queue.remove();%0A            for (int adj : adjList.get(vertex)) %7B%0A                if (!marked.contains(adj)) %7B%0A                    paths.put(adj, vertex);%0A                    queue.add(adj);%0A                    marked.add(adj);%0A                %7D%0A            %7D%0A        %7D%0A        for (int vertex = 1; vertex %3C= vertices; vertex++) %7B%0A            if (vertex == source) %7B%0A                continue;%0A            %7D%0A            int distance = 0;%0A            Integer parent = paths.get(vertex);%0A            while (parent != null) %7B%0A                distance += 6;%0A                parent = paths.get(parent);%0A            %7D%0A            if (distance == 0) %7B%0A                System.out.print(%22-1 %22);%0A            %7D else %7B%0A                System.out.print(distance + %22 %22);%0A            %7D%0A        %7D%0A        System.out.println();%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Scanner in = new Scanner(System.in);%0A        int q = in.nextInt();%0A        Map%3CInteger, Set%3CInteger%3E%3E adjList = new HashMap%3C%3E();%0A        for (int i = 0; i %3C q; i++) %7B%0A            int n = in.nextInt();%0A            int m = in.nextInt();%0A            for (int v = 1; v %3C= n; v++) %7B%0A                adjList.put(v, new HashSet%3C%3E());%0A            %7D%0A            for (int e = 0; e %3C m; e++) %7B%0A                int v1 = in.nextInt();%0A                int v2 = in.nextInt();%0A                adjList.get(v1).add(v2);%0A                adjList.get(v2).add(v1);%0A            %7D%0A            int s = in.nextInt();%0A            bfs(s, n, adjList);%0A        %7D
 %0A   

Solve BFS: Shortest Reach