(UVA) Place the Guards - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=669&page=show_problem&problem=2021

For this problem, we need to find out if the graph is bipartite. The solution below used a Breath-First Search (BFS) to accomplish this task.


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

class Main {  
    public ArrayList<ArrayList<Integer>> adjList;
    public int[] nodes;
    public int[] count;
  
    public boolean bfs(int start, int numNodes) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        nodes[start] = 0;
      
        count[0]++;
      
        while (queue.size() > 0) {
            int currNode = queue.poll();
          
            ArrayList<Integer> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                if (nodes[reachNodes.get(i)] == -1) {
                    nodes[reachNodes.get(i)] = (nodes[currNode]+1)%2;
                    count[(nodes[currNode]+1)%2]++;
                    queue.add(reachNodes.get(i));
                }
                else if (nodes[reachNodes.get(i)] == nodes[currNode]) {
                    return false;
                }
            }
        }
      
        return true;
    }
  
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numNodes = sc.nextInt();
            int numEdges = sc.nextInt();
          
            adjList = new ArrayList<>();
            for (int j = 0; j < numNodes; j++) {
                adjList.add(new ArrayList<Integer>());
            }
          
            for (int j = 0; j < numEdges; j++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
              
                adjList.get(n1).add(n2);
                adjList.get(n2).add(n1);
            }
          
            nodes = new int[numNodes];
            for (int j = 0; j < numNodes; j++) {
                nodes[j] = -1;
            }
          
            int answer = 0;
            boolean b = true;
            count = new int[2];
            for (int j = 0; j < numNodes; j++) {
                if (nodes[j] != -1) { // it was visited
                    continue;
                }
                count[0] = 0;
                count[1] = 0;
                b = bfs(j, numNodes);
                if (b == false) {
                    break;
                }
                // there are some cases like:
                // - only one node (no edges)
                // - more than one connected components
                answer += Math.max(1, Math.min(count[0], count[1]));
            }
          
            if (!b) {
                bw.write("-1\n");
            }
            else {
                bw.write(answer+"\n");
            }
        }
                                     
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}