Check whether a graph is bipartite / the Two-Clique problem

Medium

Problem

(1) Return true if the nodes can be coloured with two colours so that every edge joins different colours. (2) Two-Clique: return true if the nodes can be split into two groups, each forming a complete subgraph — which holds exactly when the complement graph is bipartite.

Example 1

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

Example 2

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

The triangle 0–1–2 cannot be 2-coloured.

Also asked as: Check whether a graph is Bipartite or Not · Two Clique Problem

Test cases

Case 1

Input:    [[1,3],[0,2],[1,3],[0,2]]
Expected: true

Case 2

Input:    [[1,2,3],[0,2],[0,1,3],[0,2]]
Expected: false

Case 3

Input:    [[]]
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. 2-colour with BFS/DFS

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

Colour a node, colour its neighbours the opposite colour. A conflict means an odd cycle ⇒ not bipartite. "Two cliques": a graph’s vertices split into two cliques iff its COMPLEMENT is bipartite.

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