Is Graph Bipartite? LeetCode solution in Java

1
class Solution {
2
  public boolean isBipartite(int[][] graph) {
3
    int n = graph.length;
4
    int[] colors = new int[n];
5

6
    // take two colors and color adjacent neighbours differently, if any of the neighbour is already
7
    // colored and is not a different color, but same color, then return false else true.
8
    for (int i = 0; i < n; i++) {
9
      if (colors[i] == 0) { // if not yet coloured.
10
        Queue<Integer> q = new LinkedList<>();
11
        q.add(i);
12
        colors[i] = 1; // color it with blue
13

14
        while (!q.isEmpty()) {
15
          int cur = q.poll(); // start polling the current node
16

17
          for (int x : graph[cur]) {
18
            if (colors[x] == 0) { // if not yet colored
19
              colors[x] = -colors[cur]; // Use a different color for the adjacent node
20
              q.offer(x);
21
            } else if (colors[x]
22
                != -colors[
23
                    cur]) // if the adjacent node/neighbour is already coloured and not a different
24
              // colour, we return false, as no two adjacent vertices must have same
25
              // colors.
26
              return false;
27
          }
28
        }
29
      }
30
    }
31
    return true;
32
  }
33
}