Bipartite check (two-coloring)

How does Bipartite check (two-coloring) work?

Start with every node uncoloured. Then loop over all of them.

An uncoloured node begins a new walk. Paint it with the first colour.

Visit each neighbour in turn. Paint an uncoloured neighbour with the opposite colour.

A neighbour that already has a colour must differ from the current node. If they match, the graph fails.

A conflict means an odd cycle exists somewhere. No two-colouring can survive one of those.

Repeat for every component. The graph is bipartite only when all of them pass.

1. colour[0] = AThe graph is a triangle: 0-1, 1-2 and 2-0.
2. colour[1] = BIts neighbour takes the other colour.
3. colour[2] = ANode 2 sits next to node 1, so it takes A.
4. edge 2-0: A against ABoth ends carry the same colour. The check fails.
5. answer = falseA triangle is an odd cycle. Two colours can never fit it.

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;
}

A worked example of Bipartite check (two-coloring)

Split people into two groups

You get a number of people and a list of pairs who dislike each other.

Split everyone into two groups so that nobody shares a group with someone they dislike.

Each person is a node and each dislike is an edge.

Run the two-colouring over every component. A single conflict makes the split impossible.

function possibleBipartition(n, dislikes) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const colour = new Array(n + 1).fill(0);

    for (let start = 1; start <= n; start++) {
        if (colour[start] !== 0) continue; // already placed by an earlier walk

        colour[start] = 1;
        const queue = [start];

        for (let i = 0; i < queue.length; i++) {
            const node = queue[i];

            for (const next of graph[node]) {
                if (colour[next] === colour[node]) return false; // same side
                if (colour[next] === 0) {
                    colour[next] = -colour[node];
                    queue.push(next);
                }
            }
        }
    }

    return true;
}

When should you use Bipartite check (two-coloring)?

These phrases in a problem statement point here:

• •split into two groups with no conflict inside a group
• •two-color the graph
• •detect an odd-length cycle
• •us vs them / two-shift scheduling / two-room assignment
• •possible bipartition of conflict pairs

What is Bipartite check (two-coloring) confused with?

• Graph BFS / DFS: The walk itself is identical. The only addition is a colour carried on each node.
• Connected components: Both loop over unvisited nodes and start a walk. Here a walk can also fail.
• Union-find (disjoint set): A weighted disjoint set answers the same question. It suits edges that arrive over time.
• Backtracking: Three or more colours needs a search with undo. Two colours never needs a choice.

Common mistakes with Bipartite check (two-coloring)

• Walking only from the first node

  A disconnected graph can hide the conflict elsewhere. Start a walk from every uncoloured node.

• Storing only a visited flag

  You need the colour, not just whether it was seen. One array can carry both.

• Colouring on removal from the queue

  The same node can then enter twice with different colours. Colour it as you push it.

• Expecting failure to look specific

  The only possible cause is an odd cycle. A graph with only even cycles always passes.

Which interview problems use Bipartite check (two-coloring)?

• Is graph bipartite: The plain form, over an adjacency list.
• Possible bipartition: Dislike pairs become the edges.
• Divide players into two teams: The same two-colouring, worded differently.
• Detect an odd cycle: The same test, asked the other way round.
• Maximum bipartite matching: Only meaningful once the two sides are known.
• Flower planting with no adjacent same: Four colours, so a greedy pass is enough.
• Graph colouring with three colours: Backtracking, since two colours no longer decide it.

What is the time and space complexity of Bipartite check (two-coloring)?

O(V+E)

V nodes and E edges give O(V + E). Each node is coloured once and each edge checked twice.