(UVA) 762 - We Ship Cheap - 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.processa();
       
        System.exit(0);
    }
   
    ArrayList<Integer> busca(ArrayList<ArrayList<Integer>> matrizAdj, int partida, int destino, int qteLocais) {
         int[] vetorVisitados = new int[qteLocais];
              
        for (int i = 0; i < qteLocais; i++) {
            vetorVisitados[i] = -1;
        }
      
        ArrayList<Vertice> filaVisitados = new ArrayList<Vertice>();
        filaVisitados.add(new Vertice(partida, -1));
      
        int verticeAtual;
       
        vetorVisitados[partida] = 1;
               
        int inicioFila = 0;
        int pai = -1;
        ArrayList<Integer> vetorResposta = new ArrayList<Integer>();
        while (filaVisitados.size() != inicioFila) {
            verticeAtual = filaVisitados.get(inicioFila).vertice;
      
            for (int i = 0; i < matrizAdj.get(verticeAtual).size(); i++) {
                int tentar = matrizAdj.get(verticeAtual).get(i);
                if (vetorVisitados[tentar] == -1) {
                    vetorVisitados[tentar] = inicioFila;
                    filaVisitados.add(new Vertice(tentar, inicioFila));
                    if (tentar == destino) {
                        vetorResposta.add(0, tentar);
                        pai = inicioFila;
                        break;
                    }
                 }
            }
            inicioFila++;
        }
      
        while (pai > -1) {
            vetorResposta.add(filaVisitados.get(pai).vertice);
            pai = filaVisitados.get(pai).pai;
        }
       
        return vetorResposta;
    }
   
    void processa() throws NumberFormatException, IOException {
        String line = "";
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int contaTeste = 0;
        while((line = br.readLine()) != null) {
            if (contaTeste == 1) {
                bw.write("\n");
            }
           
            contaTeste = 1;
           
            StringTokenizer tokenizer = new StringTokenizer(line);
            int qteLink = Integer.valueOf(tokenizer.nextToken());

            Map<String, Integer> associacao = new HashMap<String, Integer>();
            int contador = 0;
            ArrayList<ArrayList<Integer>> listaAdj = new ArrayList<ArrayList<Integer>>();
           
            String[] lugares = new String[qteLink+qteLink];
            for (int i = 0; i < qteLink; i++) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
               
                String local1 = tokenizer.nextToken();
                if (!associacao.containsKey(local1)) {
                    lugares[contador] = local1;
                    associacao.put(local1, contador);
                    contador++;    
                    listaAdj.add(new ArrayList<Integer>());          
                }

                String local2 = tokenizer.nextToken();
                if (!associacao.containsKey(local2)) {
                    lugares[contador] = local2;
                    associacao.put(local2, contador);
                    contador++;
                    listaAdj.add(new ArrayList<Integer>());
                }
               
                listaAdj.get(associacao.get(local1)).add(associacao.get(local2));
                listaAdj.get(associacao.get(local2)).add(associacao.get(local1));
            }
           
            int qteLocais = contador;
           
            boolean tmp;
                       
            line = br.readLine();
            tokenizer = new StringTokenizer(line);
           
            String saida = tokenizer.nextToken();
            int partida;
            if (tmp = associacao.containsKey(saida)) {
                partida = associacao.get(saida);
               
            }
            else {
                partida = -1;
            }
            String chegada = tokenizer.nextToken();
            int destino;
            if (tmp = associacao.containsKey(chegada)) {
                destino = associacao.get(chegada);
            }
            else {
                destino = -1;
            }
           
            ArrayList<Integer> resposta = new ArrayList<Integer>();
            if (partida >= 0 && destino >= 0 && partida != destino) {
                resposta = busca(listaAdj, partida, destino, qteLocais);
            }
            else if (partida >= 0 && destino >= 0 && partida == destino) {
                resposta.add(partida);
                resposta.add(destino);
            }
           
            if (resposta.size() > 0) {
                for (int i = resposta.size()-1; i > 0; i--) {
                    bw.write(lugares[resposta.get(i)] + " " + lugares[resposta.get(i-1)]+"\n");
                }
            }
            else {
                bw.write("No route\n");
            }
         
            br.readLine();
        }
       
        bw.flush();
        bw.close();           
        return;
    }
}