Check whether a graph is bipartite / the Two-Clique problem
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
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;}