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

If you want to see another solution for this problem, click here.

Comparing the run time between the solutions:
- The oldest solution ran in: 0.159s.
- This new solution ran in: 0.079s.


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 = 0; k < cities.size(); k++) {
            System.out.print(cities.get(k).charAt(0));
        }
        System.out.println();
    }
   
    public static ArrayList<String> bfs(String start, String goal) {
        Queue<Element> queue = new ArrayDeque<Element>();
        ArrayList<String> list = new ArrayList<String>(); // I keep one list of cities (path) from the start city to every other city [until I find my goal]
        list.add(start);
        queue.add(new Element(start, list));
       
        HashSet<String> addedToQueue = new HashSet<String>();
        addedToQueue.add(start);
       
        while (queue.size() > 0) {
            Element currElement = queue.poll();
            String currCity = currElement.city;
            ArrayList<String> currListOfCities = currElement.listOfCities;
           
            if (currCity.equals(goal)) {
                return currListOfCities;
            }

            ArrayList<String> reachables = adjList.get(currCity);
            for (int i = 0; i < reachables.size(); i++) {
                String nextCity = reachables.get(i);
                if (!addedToQueue.contains(nextCity)) {
                    ArrayList l = (ArrayList) currListOfCities.clone();
                    l.add(nextCity);
                    queue.add(new Element(nextCity, l));
                   
                    addedToQueue.add(nextCity);
                }
            }
        }
       
        return list;
    }
   
    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);
    }
}

class Element {
    String city;
    ArrayList<String> listOfCities;
   
    public Element(String city, ArrayList<String> listOfCities) {
        this.city = city;
        this.listOfCities = listOfCities;
    }
}