(UVA) All Roads Lead Where? - Solução 2

Another solution for the problem "All Roads Lead Where?". Check the previous solution here.

Now, I do not use the class Element to create my queue in the Breadth-First Search method. Instead of creating a new class to handle with the list of cities, I use a HashMap<String, String> which maps a city to its parent. When I find the goal, I iterate through the HashMap to find the path from the current node to the start node.


import java.io.*;
import java.util.*;

class Main  {
    public static HashMap<String, ArrayList<String>> adjList = new HashMap<String, ArrayList<String>>();
   
    public static void printAnswer(ArrayList<String> cities) {
        for (int k = cities.size()-1; k >= 0; k--) {
            System.out.print(cities.get(k).charAt(0));
        }
        System.out.println();
    }
   
    public static ArrayList<String> findSequenceOfParents(HashMap<String, String> parent, String currCity, String start) {
        ArrayList<String> list = new ArrayList<String>();
        list.add(currCity);
       
        String myParent = parent.get(currCity);
        while(!myParent.equals(start)) {
            list.add(myParent);
            myParent = parent.get(myParent);
        }
        list.add(myParent);
       
        return list;
    }
   
    public static ArrayList<String> bfs(String start, String goal) {
        Queue<String> queue = new ArrayDeque<String>();
        queue.add(start);
       
        HashMap<String, String> parent = new HashMap<String, String>();
       
        HashSet<String> addedToQueue = new HashSet<String>();
        addedToQueue.add(start);
       
        parent.put(start, start);
        while (queue.size() > 0) {
            String currCity = queue.poll();
           
            if (currCity.equals(goal)) {
                return findSequenceOfParents(parent, currCity, start);
            }

            ArrayList<String> reachables = adjList.get(currCity);
            for (int i = 0; i < reachables.size(); i++) {
                String nextCity = reachables.get(i);
                if (!addedToQueue.contains(nextCity)) {
                    queue.add(nextCity);
                    parent.put(nextCity, currCity);
                   
                    addedToQueue.add(nextCity);
                }
            }
        }
       
        return null;
    }
   
    public static void readRequest(Scanner sc, int numQueries) {
        for (int j = 0; j < numQueries; j++) {
            String city1 = sc.next();
            String city2 = sc.next();
           
            ArrayList<String> cities = bfs(city1, city2);   
           
            printAnswer(cities);       
        }
    }
   
    public static void checkAdjList(String city1, String city2) {
        if (!adjList.containsKey(city1)) {
            ArrayList<String> list = new ArrayList<String>();
            adjList.put(city1, list);
        }
        adjList.get(city1).add(city2);
    }
   
    public static void readEdges(Scanner sc, int numRoads) {
        for (int j = 0; j < numRoads; j++) {
            String city1 = sc.next();
            String city2 = sc.next();
           
            checkAdjList(city1, city2);
            checkAdjList(city2, city1);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        Scanner sc = new Scanner(System.in);
       
        int numTestCases = sc.nextInt();
        for (int i = 0; i < numTestCases; i++) {
            if (i > 0) {
                System.out.println();
            }
           
            int numRoads = sc.nextInt();
            int numQueries = sc.nextInt();
           
            // read edges
            readEdges(sc, numRoads);
           
            // read requests
            readRequest(sc, numQueries);
           
            adjList.clear();
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}