(UVA) Bicoloring - Solution

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

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[] nodesID;
   
    public boolean bfs(int start, int numNodes) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        nodesID[start] = 0;
       
        while (queue.size() > 0) {
            int currNode = queue.poll();
           
            ArrayList<Integer> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                if (nodesID[reachNodes.get(i)] == -1) { // not visited yet
                    nodesID[reachNodes.get(i)] = (nodesID[currNode]+1)%2;
                    queue.add(reachNodes.get(i));
                }
                else if (nodesID[reachNodes.get(i)] == nodesID[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 numNodes = sc.nextInt();
        while (numNodes != 0) {
            int numEdges = sc.nextInt();
           
            adjList = new ArrayList<>();
            for (int i = 0; i < numNodes; i++) {
                adjList.add(new ArrayList<Integer>());
            }
           
            // read edges
            for (int i = 0; i < numEdges; i++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                adjList.get(n1).add(n2);
                adjList.get(n2).add(n1);
            }              
           
            nodesID = new int[numNodes];
            for (int i = 0; i < numNodes; i++) {
                nodesID[i] = -1;
            }
           
            boolean b = bfs(0, numNodes);
            String s = b ? "BICOLORABLE." : "NOT BICOLORABLE.";
            bw.write(s+"\n");           
       
            numNodes = sc.nextInt();
        }
                                      
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}