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

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

class Main {
    class Vertice {
        public Vertice(int v, int p) {
            vertice = v;
            pai = p;
        }
        int vertice;
        int pai;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.takeInput();
       
        System.exit(0);
    }
   
    ArrayList<Integer> busca(ArrayList<ArrayList<Integer>> matrizAdj, int qteCidades, int cidadePartida, int cidadeChegada) {
        int[] vetorVisitados = new int[qteCidades];
        for (int i = 0; i < qteCidades; i++) {
            vetorVisitados[i] = 0;
        }
       
        // Marca o vértice inicial
        vetorVisitados[cidadePartida] = 1;
       
        ArrayList<Vertice> filaCidadesVisitadas = new ArrayList<Vertice>();
        // Inserir cidade de partida como visitada
        filaCidadesVisitadas.add(new Vertice(cidadePartida, -1));
       
        int inicioFila = 0;
        int pai = -1;
        ArrayList<Integer> listaResposta = new ArrayList<Integer>();
        while (filaCidadesVisitadas.size() != inicioFila) {
            int verticeAtual = filaCidadesVisitadas.get(inicioFila).vertice;
           
            // Para cada vértice que tem ligação com o verticeAtual
            for (int i = 0; i < matrizAdj.get(verticeAtual).size(); i++) {
                int vertice = matrizAdj.get(verticeAtual).get(i);
                if (vetorVisitados[vertice] == 0) {
                    vetorVisitados[vertice] = 1; // marca o vértice
                    filaCidadesVisitadas.add(new Vertice(vertice, inicioFila)); // insere o vértice na fila
                    if (vertice == cidadeChegada) {
                        listaResposta.add(vertice);
                        pai = inicioFila;
                        break;
                    }
                }
            }
            inicioFila++; // como se estivesse tirando da fila
        }

        while(pai > -1) {
            listaResposta.add(filaCidadesVisitadas.get(pai).vertice);
            pai = filaCidadesVisitadas.get(pai).pai;
        }
        
        return listaResposta;
    }
   
    void takeInput() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        String line = br.readLine();
        int qteCasosTeste = Integer.parseInt(line);
       
        br.readLine(); // lê linha em branco
       
        for (int k = 0; k < qteCasosTeste; k++) {
            if (k != 0) {
                bw.write("\n");
            }
           
            line = br.readLine();
            StringTokenizer tokenizer = new StringTokenizer(line);
            int qteEstradas = Integer.parseInt(tokenizer.nextToken());
            int qteConsultas = Integer.parseInt(tokenizer.nextToken());
       
            String[] cidades = new String[qteEstradas*2];
            String[] vetorTmp = new String[2];
            ArrayList<ArrayList<Integer>> listaAdj = new ArrayList<ArrayList<Integer>>();
            Map<String, Integer> associacao = new HashMap<String, Integer>();
           
            int contador = 0;
            for (int i = 0; i < qteEstradas; i++) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
                for (int j = 0; j < 2; j++) {
                    String cidade = tokenizer.nextToken();
               
                    if (!associacao.containsKey(cidade)) {
                        cidades[contador] = cidade;
                        associacao.put(cidade, contador);
                        contador++;
                        listaAdj.add(new ArrayList<Integer>());
                    }
                   
                    vetorTmp[j] = cidade;
                }
               
                listaAdj.get(associacao.get(vetorTmp[0])).add(associacao.get(vetorTmp[1]));
                listaAdj.get(associacao.get(vetorTmp[1])).add(associacao.get(vetorTmp[0]));
            }
           
            int qteCidades = contador;
           
            for (int i = 0; i < qteConsultas; i++) {       
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
                String cidadePartida = tokenizer.nextToken();
                String cidadeChegada = tokenizer.nextToken();
               
                ArrayList<Integer> listaResposta = new ArrayList<Integer>();
               
                listaResposta = busca(listaAdj, qteCidades, associacao.get(cidadePartida), associacao.get(cidadeChegada));
           
                for (int j = listaResposta.size()-1; j >= 0; j--) {
                    bw.write(cidades[listaResposta.get(j)].charAt(0));
                }
                bw.write("\n");
            }
            br.readLine(); // lê linha em branco
        }
       
        bw.flush();
        bw.close();
        return;
    }
}