301. Is Graph Bipartite?

Try to 2-color the graph: give each node a color opposite its neighbours. A conflict (a neighbour already has the same color) proves it is not bipartite.

Two colors, no clash

A graph is bipartite iff it can be 2-colored so no edge joins same-colored nodes. Traverse each unvisited component, coloring the start 1 and each neighbour the opposite color. If a neighbour already carries the same color, an odd cycle exists → not bipartite.

for each unvisited start:
    color[start] = 1; stack = [start]
    while stack: node = pop
        for nei: if uncolored: color = -color[node]; push
                 elif color[nei] == color[node]: return False
return True

Worked example

[[1,3],[0,2],[1,3],[0,2]] (a 4-cycle) is bipartite → true. Adding a chord that creates an odd cycle makes it false.

Complexity

• Time: O(V + E).
• Space: O(V).

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for (int start = 0; start < n; start++) {
            if (color[start] != 0) continue;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(start);
            color[start] = 1;
            while (!stack.isEmpty()) {
                int node = stack.pop();
                for (int nei : graph[node]) {
                    if (color[nei] == 0) {
                        color[nei] = -color[node];
                        stack.push(nei);
                    } else if (color[nei] == color[node]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}