Problem statement

An undirected graph is bipartite if its nodes can be split into two sets so that every edge joins a node in one set to a node in the other.

You are given the adjacency list graph, where graph[u] lists the neighbours of node u. Return true if the graph is bipartite.

Example 1

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

Example 2

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

Example 3

Input: graph = [[]]
Output: true

Constraints

• 1 <= graph.length <= 30
• The graph is undirected and has no self-loops or repeated edges.
• It may be disconnected.

Hints for Is Graph Bipartite?

1. Hint 1

   Two-colour the graph: give a start node one colour and every neighbour the other.

2. Hint 2

   BFS or DFS from every uncoloured node, since the graph may be disconnected.

3. Hint 3

   If you ever meet a neighbour that already has your own colour, it is not bipartite.

How to solve Is Graph Bipartite?

Two-colour the graph by BFS: give each neighbour the opposite colour, and fail if a neighbour already has the same colour.

Approach

1. For each uncoloured node, colour it 1 and BFS.
2. For each neighbour: colour it -color[node] if uncoloured; return false if it equals color[node].
3. Return true.

Why it works

A graph is bipartite iff it has no odd cycle, and a proper 2-colouring exists exactly then; BFS colouring finds one or exposes a conflict.

Complexity

• Time — O(V + E)
• Space — O(V)

Pitfalls

• Restart from every uncoloured node — the graph may be disconnected.

Reference solution

Python

from collections import deque

def isBipartite(graph) -> bool:
    n = len(graph)
    color = [0] * n
    for start in range(n):
        if color[start] != 0:
            continue
        color[start] = 1
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if color[nxt] == 0:
                    color[nxt] = -color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False
    return True

Java

public static 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;
        color[start] = 1;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(start);
        while (!queue.isEmpty()) {
            int node = queue.pollFirst();
            for (int next : graph[node]) {
                if (color[next] == 0) {
                    color[next] = -color[node];
                    queue.addLast(next);
                } else if (color[next] == color[node]) {
                    return false;
                }
            }
        }
    }
    return true;
}

C++

bool isBipartite(vector<vector<int>>& graph) {
    int n = (int) graph.size();
    vector<int> color(n, 0);
    for (int start = 0; start < n; start++) {
        if (color[start] != 0) continue;
        color[start] = 1;
        vector<int> queue;
        queue.push_back(start);
        size_t head = 0;
        while (head < queue.size()) {
            int node = queue[head++];
            for (int next : graph[node]) {
                if (color[next] == 0) {
                    color[next] = -color[node];
                    queue.push_back(next);
                } else if (color[next] == color[node]) {
                    return false;
                }
            }
        }
    }
    return true;
}

JavaScript

var isBipartite = function(graph) {
    const n = graph.length;
    const color = [];
    for (let i = 0; i < n; i++) color.push(0);
    for (let start = 0; start < n; start++) {
        if (color[start] !== 0) continue;
        color[start] = 1;
        const queue = [start];
        let head = 0;
        while (head < queue.length) {
            const node = queue[head++];
            for (let i = 0; i < graph[node].length; i++) {
                const next = graph[node][i];
                if (color[next] === 0) {
                    color[next] = -color[node];
                    queue.push(next);
                } else if (color[next] === color[node]) {
                    return false;
                }
            }
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Implement Magic Dictionary Medium
• Design Add and Search Words Data Structure Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium