(UVA) Dominos 2 - Solution 1

I used Depth-First Search to solve this problem.

Initially, for every domino knocked by hand, I called the DFS method. Then, in this method, I checked if the current domino would make another one to fall over. If yes, I called the DFS method for every reachable node.


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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> knocks = new HashMap<Integer, ArrayList<Integer>>();
    public static int[] visited;
   
    public static int dfs(int domino) {
        int count = 0;
       
        if (visited[domino] == 0) {
            visited[domino] = 1;
            count++;
            ArrayList<Integer> reachableDominos = knocks.get(domino);
            for (int i = 0; i < reachableDominos.size(); i++) {
                count += dfs(reachableDominos.get(i));
            }
        }
       
        return count;
    }
   
    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();
            int numKnockedDominos = sc.nextInt();
           
            // init map knocks
            for (int j = 1; j <= numDominos; j++) {
                knocks.put(j, new ArrayList<Integer>());
            }
           
            // domino d1 reaches domino d2
            for (int j = 0; j < numDependencies; j++) {
                int d1 = sc.nextInt();
                int d2 = sc.nextInt();
                knocks.get(d1).add(d2);
            }
           
            // read knocked dominos
            visited = new int[numDominos+1];
            int count = 0;
            for (int j = 0; j < numKnockedDominos; j++) {
                int domino = sc.nextInt();
                count += dfs(domino);
            }
           
            System.out.println(count);
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}