(UVA) Montesco vs Capuleto - Solution

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

For every bipartite graph, we need to find out which "side" has more nodes. 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[] state;
   
    public int bfs(int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        state[start] = 0;
       
        boolean possible = true;
       
        int stateZero = 0;
        int stateOne = 0;
        while (queue.size() > 0) {
            int currPeople = queue.poll();
            if (state[currPeople] == 0) {
                stateZero++;
            }
            else {
                stateOne++;
            }
           
            ArrayList<Integer> reachPeople = adjList.get(currPeople);
            for (int i = 0; i < reachPeople.size(); i++) {
                if (state[reachPeople.get(i)] == state[currPeople]) { // If I visited this one, and its state is equal to the current node, it is not possible to invite anyone from this connected component
                    possible = false;
                }
                if (state[reachPeople.get(i)] != -1) { // If I visited this one, I do not need to add it to the queue again
                    continue;
                }
                state[reachPeople.get(i)] = (state[currPeople]+1)%2;
                queue.add(reachPeople.get(i));
            }
        }
       
        if (!possible) {
            return -1;
        }
        return Math.max(stateZero, stateOne);
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int test = 0; test < numTests; test++) {
            int numPeople = sc.nextInt();
            adjList = new ArrayList<>();
            for (int i = 0; i < numPeople; i++) {
                adjList.add(new ArrayList<Integer>());
            }
           
            for (int i = 0; i < numPeople; i++) {
                int numEnemies = sc.nextInt();
                for (int j = 0; j < numEnemies; j++) {
                    int enemy = sc.nextInt()-1;
                    if (enemy < 0 || enemy >= numPeople) {
                        continue;
                    }
                    adjList.get(i).add(enemy);
                    adjList.get(enemy).add(i);
                }
            }
           
            state = new int[numPeople];
            Arrays.fill(state, -1);
            int sum = 0;
            for (int i = 0; i < numPeople; i++) {
                if (state[i] != -1) {
                    continue;
                }
                int b = bfs(i);
                if (b == -1) {
                    continue;
                }
                sum += b;
            }
           
            System.out.println(sum);
        }
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}