(UVA) Dominos 2 - Solution 2

I used Breadth-First Search to solve this problem.

If you want to see this problem solved using Depth-First Search, click here.

Initially, I added all the dominos knocked over by hand in a Queue. Then, in the BFS method, for every domino already knocked I checked if it would make another domino to fall over. If yes, I added this domino to the Queue. Besides, every knocked domino was stored in a HashSet in order to do not have any domino considered more than once and to give the total number of dominos that fell over. 


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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> knocks = new HashMap<Integer, ArrayList<Integer>>();
  
    public static int bfs(Queue<Integer> knockedDominos, HashSet<Integer> considered) {
        while (knockedDominos.size() > 0) {
            int currDomino = knockedDominos.poll();
          
            ArrayList<Integer> reachDominos = knocks.get(currDomino);
            for (int i = 0; i < reachDominos.size(); i++) {
                int nextDomino = reachDominos.get(i);
                if (!considered.contains(nextDomino)) {
                    knockedDominos.add(nextDomino);
                    considered.add(nextDomino);
                }
            }
        }
      
        return considered.size();
    }
  
    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 falls domino d2
            for (int j = 0; j < numDependencies; j++) {
                int d1 = sc.nextInt();
                int d2 = sc.nextInt();
                knocks.get(d1).add(d2);
            }
          
            Queue<Integer> knockedDominos = new ArrayDeque<Integer>();
            HashSet<Integer> considered = new HashSet<Integer>();
            for (int j = 0; j < numKnockedDominos; j++) {
                int domino = sc.nextInt();
                knockedDominos.add(domino);
                if (!considered.contains(domino)) {
                    considered.add(domino);
                }
            }
          
            System.out.println(bfs(knockedDominos, considered));
        }
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}