(UVA) Calling Circles - Solution

I used Kosaraju's algorithm to solve this problem.


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

class Main {
    public static HashMap<String, Integer> map;
    public static HashMap<String, ArrayList<String>> adjListOut;
    public static HashMap<String, ArrayList<String>> adjListOutReverse;
    public static HashMap<Integer, ArrayList<String>> circles;
    public static Deque<String> stack;
    public static boolean[] visited;
   
    public static void dfsReverse(int index, String name) {
        if (visited[map.get(name)]) {
            return;
        }
       
        visited[map.get(name)] = true;
        if (adjListOutReverse.get(name) == null) {
            circles.get(index).add(name);
            return;
        }
        ArrayList<String> calls = adjListOutReverse.get(name);
        for (int i = 0; i < calls.size(); i++) {
            dfsReverse(index, calls.get(i));
        }
       
        circles.get(index).add(name);
    }
   
    public static void dfs(String name) {
        if (visited[map.get(name)]) {
            return;
        }
       
        visited[map.get(name)] = true;
        if (adjListOut.get(name) == null) {
            stack.add(name);
            return;
        }
        ArrayList<String> calls = adjListOut.get(name);
        for (int i = 0; i < calls.size(); i++) {
            dfs(calls.get(i));
        }
       
        stack.add(name);
    }
   
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
        String line = br.readLine();
        String[] s = line.split("\\s");
        int numPeople = Integer.parseInt(s[0]);
        int numCalls = Integer.parseInt(s[1]);
        while (numPeople != 0 || numCalls != 0) {
            if (numCase > 0) {
                System.out.println();
            }
           
            map = new HashMap<String, Integer>();
            adjListOut = new HashMap<String, ArrayList<String>>();
            adjListOutReverse = new HashMap<String, ArrayList<String>>();
           
            int index = 0;        
            for (int i = 0; i < numCalls; i++) {
                line = br.readLine();
                s = line.split("\\s");
                String c1 = s[0];
                String c2 = s[1];
               
                if (!map.containsKey(c1)) {
                    map.put(c1, index++);
                }
                if (!map.containsKey(c2)) {
                    map.put(c2, index++);
                }
               
                if (!adjListOut.containsKey(c1)) {
                    adjListOut.put(c1, new ArrayList<String>());
                }
                adjListOut.get(c1).add(c2);
               
                if (!adjListOutReverse.containsKey(c2)) {
                    adjListOutReverse.put(c2, new ArrayList<String>());
                }
                adjListOutReverse.get(c2).add(c1);
            }
           
            visited = new boolean[numPeople];
            stack = new ArrayDeque<String>();
            for (String name : map.keySet()) {
                dfs(name);
            }
           
            index = 0;
            int stackSize = stack.size();
            visited = new boolean[numPeople];
            circles = new HashMap<Integer, ArrayList<String>>();
            for (int i = 0; i < stackSize; i++) {
                String name = stack.pollLast();
                if (!visited[map.get(name)]) {
                    circles.put(index, new ArrayList<String>());
                    dfsReverse(index, name);
                    index++;
                }
            }
           
            System.out.println("Calling circles for data set " + ++numCase + ":");
            for (int i = 0; i < index; i++) {
                ArrayList<String> callingCircles = circles.get(i);
                for (int j = 0; j < callingCircles.size()-1; j++) {
                    System.out.print(callingCircles.get(j) + ", ");
                }
                System.out.println(callingCircles.get(callingCircles.size()-1));
            }
           
            line = br.readLine();
            s = line.split("\\s");           
            numPeople = Integer.parseInt(s[0]);
            numCalls = Integer.parseInt(s[1]);
        }
                                             
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}