BitGo

// Java program to find shortest path in an undirected
// graph
import java.util.*;

public class pathUnweighted {



    static Map<String,Integer> mp = new HashMap<>();
    static Map<Integer,String> rmp = new HashMap<>();
    public static String GraphChallenge(String[] strArr) {

        int n =  Integer.parseInt(strArr[0]);

        int v = n+1;
        ArrayList<ArrayList<Integer>> adj =
                new ArrayList<ArrayList<Integer>>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<Integer>());
        }


        for(int i=1;i<=n;i++) {
            mp.put(strArr[i],Integer.valueOf(i));
            rmp.put(Integer.valueOf(i),strArr[i]);
        }
//        {"5","A","B","C","D","F","A-B","A-C","B-C","C-D","D-F"};
        for(int i=n+1;i<strArr.length;i++){
            String []nodes =  strArr[i].split("-");
            int src  = mp.get(nodes[0]).intValue();
            int dest = mp.get(nodes[1]).intValue();
            addEdge(adj, src, dest);
        }
        int source = mp.get(strArr[1]).intValue();
        int dest   = mp.get(strArr[n]).intValue();
        return printShortestDistance(adj, source, dest, v);

    }

    // Driver Program
    public static void main(String args[])
    {
        Scanner s = new Scanner(System.in);
        String[] s1 =  {"9","Z","B","C","D","R","A","Y","Q","E","A-Z","A-R","Z-Y","Z-C","C-B","Y-Q","Q-D","D-E","R-E"};
        String ans = GraphChallenge(s1);
        System.out.println(ans);
    }

    // function to form edge between two vertices
    // source and dest
    private static void addEdge(ArrayList<ArrayList<Integer>> adj, int i, int j)
    {
        adj.get(i).add(j);
        adj.get(j).add(i);
    }

    // function to print the shortest distance and path
    // between source vertex and destination vertex
    private static String printShortestDistance(
            ArrayList<ArrayList<Integer>> adj,
            int s, int dest, int v)
    {


        String ans="";
        int pred[] = new int[v];
        int dist[] = new int[v];

        if (BFS(adj, s, dest, v, pred, dist) == false) {
//            System.out.println("Given source and destination" +"are not connected");
            ans = "-1";
            return ans;
        }

        // LinkedList to store path
        LinkedList<Integer> path = new LinkedList<Integer>();
        int crawl = dest;
        path.add(crawl);
        while (pred[crawl] != -1) {
            path.add(pred[crawl]);
            crawl = pred[crawl];
        }

        // Print distance
//        System.out.println("Shortest path length is: " + dist[dest]);

        // Print path
//        System.out.println("Path is ::");
        for (int i = path.size() - 1; i > 0; i--) {
                String test = rmp.get(path.get(i));
                ans = ans + test + "-";
            //            System.out.print(path.get(i) + " ");
        }
        ans = ans + rmp.get(path.get(0));
        return ans;
    }


    private static boolean BFS(ArrayList<ArrayList<Integer>> adj, int src,
                               int dest, int v, int pred[], int dist[])
    {

        LinkedList<Integer> queue = new LinkedList<Integer>();

        boolean visited[] = new boolean[v];


        for (int i = 0; i < v; i++) {
            visited[i] = false;
            dist[i] = Integer.MAX_VALUE;
            pred[i] = -1;
        }

        visited[src] = true;
        dist[src] = 0;
        queue.add(src);

        while (!queue.isEmpty()) {
            int u = queue.remove();
            for (int i = 0; i < adj.get(u).size(); i++) {
                if (visited[adj.get(u).get(i)] == false) {
                    visited[adj.get(u).get(i)] = true;
                    dist[adj.get(u).get(i)] = dist[u] + 1;
                    pred[adj.get(u).get(i)] = u;
                    queue.add(adj.get(u).get(i));

                    // stopping condition (when we find
                    // our destination)
                    if (adj.get(u).get(i) == dest)
                        return true;
                }
            }
        }
        return false;
    }
}