(UVA) The Net - Solution

I used Breadth-First Search to solve this problem.


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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjList;
   
    public static String bfs(int start, int end) {
        Queue<Path> queue = new ArrayDeque<Path>();
        Path p = new Path(start, "");
        queue.add(p);
       
        HashSet<Integer> addedToQueue = new HashSet<Integer>();
        addedToQueue.add(start);
       
        while (queue.size() > 0) {
            Path currPath = queue.poll();
            int currRouter = currPath.router;
            String parents = currPath.parents;

            String s = parents+" "+currRouter;
            if (currRouter == end) {
                return s;           
            }
           
            ArrayList<Integer> reachRouters = adjList.get(currRouter);
            for (int i = 0; i < reachRouters.size(); i++) {
                int nextRouter = reachRouters.get(i);
                if (!addedToQueue.contains(nextRouter)) {
                    p = new Path(nextRouter, s);
                    queue.add(p);
                    addedToQueue.add(nextRouter);
                }
            }
        }
       
        return "";
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        String line = br.readLine();
        while (line != null) {
            int numRouters = Integer.parseInt(line);
            adjList = new HashMap<Integer, ArrayList<Integer>>();
            for (int i = 1; i <= numRouters; i++) {
                adjList.put(i, new ArrayList<Integer>());
            }
           
            for (int i = 0; i < numRouters; i++) {
                line = br.readLine();
                String[] s = line.split("-");
                int router = Integer.parseInt(s[0]);
                if (s.length > 1) {
                    String[] s2 = s[1].split(",");
                    for (int j = 0; j < s2.length; j++) {
                        adjList.get(router).add(Integer.parseInt(s2[j]));
                    }
                }
            }
           
            line = br.readLine();
            int numQueries = Integer.parseInt(line);
            System.out.println("-----");
            for (int i = 0; i < numQueries; i++) {
                line = br.readLine();
                String[] s = line.split("\\s");
                int router1 = Integer.parseInt(s[0]);
                int router2 = Integer.parseInt(s[1]);
               
                String listRouters = bfs(router1, router2);

                if (listRouters.length() == 0) {
                    System.out.println("connection impossible");
                }
                else {
                    System.out.println(listRouters.substring(1, listRouters.length()));
                }
            }
           
            line = br.readLine();
        }
                                            
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Path {
    int router;
    String parents;
   
    public Path(int r, String p) {
        router = r;
        parents = p;
    }
}