Problem 37.4 · Advanced Graph AlgorithmsMedium

Is Graph Bipartite?

What it teaches: Two-colouring with BFS, checking every component.

Practise it on judges as “Is Graph Bipartite?”.

In plain words

Can you paint every node red or blue so that every edge joins a red and a blue node? Paint a starting node red, then paint each neighbour the opposite colour, spreading out with BFS. If you ever find an edge with the same colour on both ends, it's impossible.

Return true if the graph can be split this way. Example: [[1,3],[0,2],[1,3],[0,2]] → true.

The problem

Given an undirected graph as adjacency lists, return true if its nodes can be split into two sets with every edge between the sets.

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

Constraints

1 ≤ n ≤ 100
May be disconnected

Pattern clues in the wording

→ Two groups, edges only across

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public boolean isBipartite(int[][] graph) {
        return false;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	graph = [[1,2,3],[0,2],[0,1,3],[0,2]]	false
2	graph = [[1,3],[0,2],[1,3],[0,2]]	true

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. BFS colouring · O(V + E)

BFS colouring

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

color[] = 0 unvisited, ±1 colours. BFS each uncoloured node; conflict → false.

▶ Dry run: BFS two-colouringgraph = [[1,3],[0,2],[1,3],[0,2]]

colour(map)

0: red

queue(queue)

Step 1/4Paint node 0 red and put it in the queue.

Approach 1

import java.util.*;

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] == color[u]) return false;
                    if (color[v] == 0) { color[v] = -color[u]; q.offer(v); }
                }
            }
        }
        return true;
    }
}

Verdict: Standard.

Before you submit

Edge cases and common mistakes

Test these inputs

Disconnected graph
Isolated nodes
Triangle (false)

Mistakes people make

Only checking the component containing node 0.

Interview

Follow-up questions

How is bipartiteness used in matching?

Command Palette

The problem

Approaches

BFS colouring

Edge cases and common mistakes

Follow-up questions