(UVA) Lighting Away - Solution

I used Kosaraju's algorithm to solve this problem.


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

class Main {
    public static HashMap<Integer, ArrayList<Integer>> adjListOut;
    public static HashMap<Integer, ArrayList<Integer>> adjListOutReverse;
    public static Deque<Integer> seq;
    public static boolean[] visited;
    public static int[] idt;
    public static int count;
   
    public static void dfsReverse(int node, int identity) {
        if (visited[node]) {
            return;
        }
       
        idt[node] = identity;
        visited[node] = true;
        ArrayList<Integer> reachNodes = adjListOutReverse.get(node);
        for (int i = 0; i < reachNodes.size(); i++) {
            dfsReverse(reachNodes.get(i), identity);
        }
    }
   
    public static void dfs(int node) {
        if (visited[node]) {
            return;
        }
       
        visited[node] = true;
        ArrayList<Integer> reachNodes = adjListOut.get(node);
        for (int i = 0; i < reachNodes.size(); i++) {
            dfs(reachNodes.get(i));
        }
        seq.add(node);
    }
   
    public static int reader (BufferedReader br) throws NumberFormatException, IOException {
        int n;
        int resp = 0;
        
        while (true) {
            n = br.read();
            if (n >= '0' && n <= '9') break;
        }
        while (true) {
            resp = resp*10 + n-'0';
            n = br.read();
            if (n < '0' || n > '9') break;
        }
        
        return resp;
    }
   
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numTests = reader(br);
        for (int i = 0; i < numTests; i++) {
            int numLights = reader(br);
            int numConnections = reader(br);
            adjListOut = new HashMap<Integer, ArrayList<Integer>>();
            adjListOutReverse = new HashMap<Integer, ArrayList<Integer>>();
            for (int j = 1; j <= numLights; j++) {
                adjListOut.put(j, new ArrayList<Integer>());
                adjListOutReverse.put(j, new ArrayList<Integer>());
            }
           
            for (int j = 0; j < numConnections; j++) {
                int n1 = reader(br);
                int n2 = reader(br);
                adjListOut.get(n1).add(n2);
                adjListOutReverse.get(n2).add(n1);
            }
           
            visited = new boolean[numLights+1];
            seq = new ArrayDeque<Integer>();
            for (int j = 1; j <= numLights; j++) {
                dfs(j);
            }
           
            count = 0;
            visited = new boolean[numLights+1];
            idt = new int[numLights+1];
            int seqSize = seq.size();
            for (int j = 0; j < seqSize; j++) {
                int node = seq.pollLast();
                if (!visited[node]) {
                    dfsReverse(node, count);
                    count++;
                }
            }
           
            int[] degrees = new int[count];
            for (int j = 1; j <= numLights; j++) {
                ArrayList<Integer> reachNodes = adjListOut.get(j);
                for (int k = 0; k < reachNodes.size(); k++) {
                    int next = reachNodes.get(k);
                    if (idt[j] != idt[next]) {
                        degrees[idt[next]]++;
                    }
                }
            }
           
            int countZeroDegree = 0;
            for (int j = 0; j < count; j++) {
                if (degrees[j] == 0) {
                    countZeroDegree++;
                }
            }
           
            System.out.println("Case " + (i+1) + ": " + countZeroDegree);
        }
                                             
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}