(UVA) Dominos - Solution

In order to solve this problem, I used Kosaraju's algorithm, which helps to find the strongly connected components.

Each strongly connected component was associated with an identification. Then, I used these identifications to check if two dominos were in the same connected component. If not, the connected component of the domino to be reached would have its degree increased.

The answer is the number of connected components whose degree is equal to zero.


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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjListOut;
    public static HashMap<Integer, ArrayList<Integer>> adjListOutReverse;
    public static HashMap<Integer, Integer> identities;
    public static Deque<Integer> stack;
    public static boolean[] visited;
   
    public static void dfsReverse(int vertex, int idt) {
        if (visited[vertex]) {
            return;
        }
       
        identities.put(vertex, idt);
       
        visited[vertex] = true;
        ArrayList<Integer> neighbors = adjListOutReverse.get(vertex);
        for (int i = 0; i < neighbors.size(); i++) {
            dfsReverse(neighbors.get(i), idt);
        }
    }
   
    public static void dfs(int vertex) {
        if (visited[vertex]) {
            return;
        }
       
        visited[vertex] = true;
        ArrayList<Integer> neighbors = adjListOut.get(vertex);
        for (int i = 0; i < neighbors.size(); i++) {
            dfs(neighbors.get(i));
        }
        stack.add(vertex);
    }
   
    public static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numDominos = sc.nextInt();
            int numDependencies = sc.nextInt();
           
            adjListOut = new HashMap<Integer, ArrayList<Integer>>();
            adjListOutReverse = new HashMap<Integer, ArrayList<Integer>>();
            identities = new HashMap<Integer, Integer>();
            for (int j = 1; j <= numDominos; j++) {
                adjListOut.put(j, new ArrayList<Integer>());
                adjListOutReverse.put(j, new ArrayList<Integer>());
            }
           
            for (int j = 0; j < numDependencies; j++) {
                int d1 = sc.nextInt();
                int d2 = sc.nextInt();
                adjListOut.get(d1).add(d2);
                adjListOutReverse.get(d2).add(d1);
            }
           
            // Kosaraju's algorithm
            visited = new boolean[numDominos+1];
            stack =  new ArrayDeque<Integer>();
            for (int j = 1; j <= numDominos; j++) {
                dfs(j);
            }

            int count = 0;
            int stackSize = stack.size();
            visited = new boolean[numDominos+1];
            for (int j = 0; j < stackSize; j++) {
                int domino = stack.pollLast();
                if (!visited[domino]) {
                    dfsReverse(domino, count);
                    count++;
                }
            }
           
            int[] degrees = new int[count];
            for (int j = 1; j <= numDominos; j++) {
                ArrayList<Integer> reachDominos = adjListOut.get(j);
                for (int k = 0; k < reachDominos.size(); k++) {
                    int nextDomino = reachDominos.get(k);
                    if (identities.get(j) != identities.get(nextDomino)) { // if they are not in the same connected component
                        degrees[identities.get(nextDomino)]++;
                    }
                }
            }
           
            int countZeroDegree = 0;
            for (int j = 0; j < count; j++) {
                if (degrees[j] == 0) {
                    countZeroDegree++;
                }
            }
           
            System.out.println(countZeroDegree);
        }
                                                
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class ConnectedComponents {
    HashSet<Integer> set;
    int idt;
   
    public ConnectedComponents(HashSet<Integer> set, int idt) {
        this.set = set;
        this.idt = idt;
    }
}