Bipartite check (two-coloring)

O(V+E)

Two-color the graph by BFS/DFS: paint the start node one color, paint every neighbor the other color, and continue outward. Reaching an edge whose two ends already share a color proves an odd-length cycle, so no two-way split exists.

Signals

split into two groups with no conflict inside a grouptwo-color the graphdetect an odd-length cycleus vs them / two-shift scheduling / two-room assignmentpossible bipartition of conflict pairs

Template

function isBipartite(n, adj) {
    const color = new Array(n).fill(-1);
    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue;
        color[start] = 0;
        const queue = [start];
        while (queue.length) {
            const node = queue.shift();
            for (const next of adj[node] || []) {
                if (color[next] === -1) {
                    color[next] = 1 - color[node];
                    queue.push(next);
                } else if (color[next] === color[node]) {
                    return false; // same color on both ends: odd cycle
                }
            }
        }
    }
    return true;
}

Looks similar, isn't

Connected components: Two-coloring checks there is no conflict inside a group and no odd cycle, more than just counting how many separate groups exist.
Union-find: Union-find tells you what is connected, but it has no notion of 'opposite side', so it cannot catch an odd cycle. Two-coloring plus the same-color clash check is what spots it.

V, E up to ~1e5, conflict pairs must split into two groups -> O(V+E): a two-color BFS/DFS sweep visits every node and edge once, and fails fast on the first same-color edge.

Learn this pattern