The problem. An undirected graph has n vertices, 0 to n - 1, and graph[u] lists the neighbours of u. The graph may be in several pieces. Return true if the vertices can be split into two teams so that every edge joins a vertex of one team to a vertex of the other — that's a bipartite graph.
graph = [[1,3],[0,2],[1,3],[0,2]] -> true (teams {0,2} and {1,3})
graph = [[1,2,3],[0,2],[0,1,3],[0,2]] -> false (0, 1, 2 form a triangle)
graph = [[1],[0],[]] -> true (vertex 2 can join either team)Give each team a colour. Pick any vertex and colour it 0. Now there's no choice left: each of its neighbours must be 1, each of their neighbours must be 0, and so on through the whole piece. So just walk the graph — BFS works well — giving every new vertex the opposite colour of the vertex that found it.
If the walk ever finds an edge whose two ends already have the same colour, the graph can't be bipartite: every colour on the way was forced, so no other choice could have avoided the clash. That clash always comes from a cycle of odd length — a graph is bipartite exactly when it has no odd cycle.
A new piece of the graph is the one place you do get a choice: nothing connects it to what's already coloured, so start it with colour 0 too.
There are 2ⁿ ways to put n vertices into two teams. Try each one — bit i of a number is the colour of vertex i — and check every edge.
function isBipartite(graph) { const n = graph.length; for (let mask = 0; mask < 1 << n; mask++) { // bit u = the colour of vertex u let ok = true; for (let u = 0; u < n && ok; u++) { for (const v of graph[u]) { if (((mask >> u) & 1) === ((mask >> v) & 1)) { // same colour on both ends ok = false; break; } } } if (ok) return true; } return false;}Time O(2ⁿ · (V + E)), space O(1). Every colouring is checked against every edge. Fine for 10 vertices, hopeless for 100 — and it ignores the fact that one vertex's colour decides all the others.
Keep a color array, -1 for not coloured yet. For every uncoloured vertex, start a BFS that colours it 0; each vertex taken from the queue gives its uncoloured neighbours the other colour, and checks that its coloured neighbours really do have the other colour.
Every colour after the first is forced. Try the odd cycle to see the clash.
function isBipartite(graph) { const n = graph.length; const color = new Array(n).fill(-1); // -1: not coloured yet for (let s = 0; s < n; s++) { if (color[s] !== -1) continue; // already coloured by an earlier search color[s] = 0; const queue = [s]; let head = 0; while (head < queue.length) { const u = queue[head++]; for (const v of graph[u]) { if (color[v] === -1) { color[v] = 1 - color[u]; // a neighbour must take the other colour queue.push(v); } else if (color[v] === color[u]) { return false; // both ends of an edge share a colour } } } } return true;}Time O(V + E), space O(V). Each vertex is coloured and queued once, and each edge is checked from both ends. A DFS that passes the colour down works just as well; BFS simply avoids deep recursion.
The jump from exponential to linear comes from one observation: after the first vertex of each piece, no colour is ever a choice.
graph[u] is empty; it fits in either team.false.true: trees have no cycles at all, so nothing can clash.