(UVA) Claw Decomposition - Solution

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

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 boolean bfs(int start, int numNodes) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        nodes[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 (nodes[reachNodes.get(i)] == -1) { // not visited yet
                    nodes[reachNodes.get(i)] = (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 numNodes = sc.nextInt();
        while (numNodes != 0) {
            adjList = new ArrayList<>();
            for (int i = 0; i <= numNodes; i++) {
                adjList.add(new ArrayList<Integer>());
            }
           
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            while (n1 != 0 || n2 != 0) {
                adjList.get(n1).add(n2);
                adjList.get(n2).add(n1);
               
                n1 = sc.nextInt();
                n2 = sc.nextInt();
            }
           
            nodes = new int[numNodes+1];
            for (int i = 0; i <= numNodes; i++) {
                nodes[i] = -1;
            }
           
            boolean b = bfs(1, numNodes);
            String s = b ? "YES" : "NO";
            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);
    }
}