#147

Is Graph Bipartite?

medium

depth-first-searchbreadth-first-searchunion-findgraph

You are given an undirected graph on n nodes labelled 0 to n - 1, as an adjacency list graph: graph[u] is the array of nodes directly connected to node u. The graph may be disconnected.

A graph is bipartite if its nodes can be split into two groups A and B such that every edge joins a node in A to a node in B — no edge lies within a single group. Equivalently, the graph can be 2-coloured with no two adjacent nodes sharing a colour.

Return true if the graph is bipartite, otherwise false.

Example

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Nodes 0,1,2 form a triangle (an odd cycle), which can never be 2-coloured.

Constraints

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] does not contain u (no self-loops) and contains no duplicates.
The graph is undirected: if v is in graph[u], then u is in graph[v].

Intuition

A graph is bipartite when its nodes split into two groups with every edge crossing between them — equivalently, it can be 2-coloured with no two neighbours sharing a colour. A first instinct is to try every possible 2-colouring and check each, but with n nodes that's 2ⁿ assignments — hopeless.

function isBipartite(graph) {
  const n = graph.length;
  // Try every way to paint the n nodes with 2 colours.
  for (let mask = 0; mask < (1 << n); mask++) {
    let ok = true;
    for (let u = 0; u < n && ok; u++) {
      for (const v of graph[u]) {
        // Same colour on both ends of an edge → this assignment fails.
        if (((mask >> u) & 1) === ((mask >> v) & 1)) { ok = false; break; }
      }
    }
    if (ok) return true;
  }
  return false;
}

Brute force — test all 2^n colour assignments for a valid one: exponential.

Enumerating colourings throws away all structure. Can we do better?

The key observation: a colouring isn't free — the moment you colour one node, every neighbour's colour is forced (the opposite). So we never guess: pick any node, colour it, BFS outward giving each newly-seen node the colour opposite its parent, and the instant an edge connects two same-coloured nodes, the graph isn't bipartite. Because the graph may be disconnected, restart from every still-uncoloured node. This is a single O(V + E) traversal — the conflict it's hunting for is an odd-length cycle, the one thing that can't be 2-coloured.

A general graph has no faithful lane or grid animation, so a static picture serves better than a misleading one. The example below is the odd cycle that fails: nodes 0,1,2 form a triangle.

Colour 0 = A. Its neighbours 1, 2, 3 must be B. But edge 1—2 joins two B nodes (1 and 2 are also neighbours) — a same-colour edge, so the BFS reports false. The culprit is the odd cycle 0–1–2–0; an even cycle like 0–1–2–3–0 would alternate A,B,A,B cleanly and pass.

Colour 0 means "uncoloured", not group A. The stored solution uses 1 and -1 for the two groups and 0 for unseen, so a single array tracks both the visited state and the colour. A neighbour gets -color[u] — the negation flips the group.
Restart per component. A bipartite even cycle plus a separate odd triangle is not bipartite; the outer loop over every node is what catches a violation hiding in a second component.

Optimization

2-colouring via BFS

Try to 2-colour the graph. Keep a color array (0 = uncoloured, 1 and -1 the two groups). Because the graph may be disconnected, start a fresh colouring from every still-uncoloured node.

From a start node, run a BFS: colour the start, then for each neighbour, if it is uncoloured give it the opposite colour and enqueue it; if it is already coloured the same as the current node, an edge lies inside a group — the graph is not bipartite, return false. If every component colours cleanly, return true.

O(V + E) time — each node and edge is examined once — and O(V) space for the colour array and queue.

function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(0);   // 0 = uncoloured; 1 / -1 are the two groups

  for (let start = 0; start < n; start++) {
    if (color[start] !== 0) continue;   // already handled in an earlier component
    color[start] = 1;
    const queue = [start];
    while (queue.length > 0) {
      const u = queue.shift();
      for (const v of graph[u]) {
        if (color[v] === 0) {
          color[v] = -color[u];         // neighbours must take the opposite group
          queue.push(v);
        } else if (color[v] === color[u]) {
          return false;                 // an edge inside one group — not bipartite
        }
      }
    }
  }
  return true;
}

Complexity analysis

Time complexity: O(V + E). Here's why:

The outer loop starts a BFS in each component, and across all of them every node is enqueued once.
Each node's adjacency list is scanned once, totalling every edge (twice, undirected).

One pass over nodes and edges — O(V + E).

Space complexity: O(V). Here's why:

The color array is one entry per node, O(V).
The BFS queue holds at most O(V) nodes.

So the extra space is O(V).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
graph =	true	A single node with no edges — trivially bipartite.
graph = [[1,2],[0],[0]]	true	A path 1–0–2 (a tree) is always 2-colourable.
graph = [[1,2,3],[0,2],[0,1],[0]]	false	A triangle on {0,1,2} with an extra leaf — the odd cycle still fails it.
graph = 23 23 01 01	true	Complete bipartite K(2,2): groups {0,1} and {2,3}, every edge crosses.
graph = [[1],[0,2],[1,3],[2,4],[3],[6],[5]]	true	A long even path plus a separate edge — both components colour, so bipartite.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor