Is Graph Bipartite?

medium graph union find dfs bfs

Problem

Given an undirected graph as adjacency lists (graph[i] = neighbors of i), return true if it is bipartite — i.e. the nodes can be split into two disjoint sets so every edge has endpoints in different sets.

Inputgraph = [[1,3],[0,2],[1,3],[0,2]]

Outputtrue

Color {0,2} red and {1,3} blue — every edge crosses colors.

adjacency (rows ;, neighbors ,)

from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [0] * n
    for s in range(n):
        if color[s] != 0:
            continue
        color[s] = 1
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == 0:
                    color[v] = -color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(0);
  for (let s = 0; s < n; s++) {
    if (color[s] !== 0) continue;
    color[s] = 1;
    const q = [s];
    while (q.length) {
      const u = q.shift();
      for (const v of graph[u]) {
        if (color[v] === 0) { color[v] = -color[u]; q.push(v); }
        else if (color[v] === color[u]) return false;
      }
    }
  }
  return true;
}

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1;
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == 0) { color[v] = -color[u]; q.offer(v); }
                    else if (color[v] == color[u]) return false;
                }
            }
        }
        return true;
    }
}

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0);
        for (int s = 0; s < n; s++) {
            if (color[s] != 0) continue;
            color[s] = 1;
            queue<int> q; q.push(s);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : graph[u]) {
                    if (color[v] == 0) { color[v] = -color[u]; q.push(v); }
                    else if (color[v] == color[u]) return false;
                }
            }
        }
        return true;
    }
};

Explanation

A graph is bipartite if we can split its nodes into two teams so that every edge goes between teams, never within one. The natural test is to try a 2-coloring with BFS and see if any edge ever connects two same-colored nodes.

We keep a color array where 0 means uncolored, and 1 / -1 are the two teams. We loop over every node as a potential start, because the graph might have several disconnected pieces, and color any still-uncolored one with 1.

From that start we run BFS. When we pop a node u and look at neighbor v: if v is uncolored, we paint it the opposite color with color[v] = -color[u] and enqueue it. If v already has the same color as u, an edge links two members of the same team, so we return false.

Example: graph = [[1,3],[0,2],[1,3],[0,2]]. Coloring node 0 red forces 1 and 3 blue, which forces 2 red — every edge crosses colors with no conflict, so the answer is true.

If all components get fully two-colored without a clash, the graph is bipartite. Each node and edge is examined once, keeping it linear.

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