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.

Sources: Wikipedia: Bipartite graph

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

function isBipartite(n: number, adj: number[][]): boolean {
    const color = new Array<number>(n).fill(-1);
    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue;
        color[start] = 0;
        const queue: number[] = [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;
}

from collections import deque

def is_bipartite(n, adj):
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in adj.get(node, []):
                if color[nxt] == -1:
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # same color on both ends: odd cycle
    return True

function isBipartite(int $n, array $adj): bool {
    $color = array_fill(0, $n, -1);
    for ($start = 0; $start < $n; $start++) {
        if ($color[$start] !== -1) continue;
        $color[$start] = 0;
        $queue = [$start];
        while ($queue) {
            $node = array_shift($queue);
            foreach ($adj[$node] ?? [] as $next) {
                if ($color[$next] === -1) {
                    $color[$next] = 1 - $color[$node];
                    $queue[] = $next;
                } elseif ($color[$next] === $color[$node]) {
                    return false; // same color on both ends: odd cycle
                }
            }
        }
    }
    return true;
}

    public static boolean isBipartite(int n, List<List<Integer>> adj) {
        int[] color = new int[n];
        Arrays.fill(color, -1);
        for (int start = 0; start < n; start++) {
            if (color[start] != -1) continue;
            color[start] = 0;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int next : adj.get(node)) {
                    if (color[next] == -1) {
                        color[next] = 1 - color[node];
                        queue.add(next);
                    } else if (color[next] == color[node]) {
                        return false; // same color on both ends: odd cycle
                    }
                }
            }
        }
        return true;
    }

    public static bool IsBipartite(int n, List<List<int>> adj) {
        var color = new int[n];
        Array.Fill(color, -1);
        for (int start = 0; start < n; start++) {
            if (color[start] != -1) continue;
            color[start] = 0;
            var queue = new Queue<int>();
            queue.Enqueue(start);
            while (queue.Count > 0) {
                int node = queue.Dequeue();
                foreach (int next in adj[node]) {
                    if (color[next] == -1) {
                        color[next] = 1 - color[node];
                        queue.Enqueue(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)?

Use Bipartite check (two-coloring) when the problem statement says “split into two groups with no conflict inside a group”, “two-color the graph” or “detect an odd-length cycle”. A solution built on it usually runs in O(V+E).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

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

Bipartite check (two-coloring) is most often confused with Graph BFS / DFS, Connected components, Union-find (disjoint set) and Backtracking.

• 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)?

Interview problems solved with Bipartite check (two-coloring) include Is graph bipartite, Possible bipartition, Divide players into two teams, Detect an odd cycle, Maximum bipartite matching, Flower planting with no adjacent same and Graph colouring with three colours.

• 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)?

The target complexity of Bipartite check (two-coloring) is O(V+E).

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