cf.completefrontend
GRAPHS · CORE

Bipartite check (two-coloring)

Check whether the nodes can be split into two groups so that every edge connects the two groups, by coloring neighbors opposite colors.

Time O(n + e)Space O(n + e)4 practice problemsStep-through picture

The idea

A graph is bipartite if you can put every node into one of two groups so that no edge connects two nodes in the same group. Think of edges as "these two must be on different teams". The question is whether two teams are enough.

The check is a BFS (or DFS) that gives colors as it goes. Give the first node side 0. Every neighbor must be on side 1, every neighbor of those on side 0, and so on. If you ever find an edge whose two ends got the same side, two teams are not enough.

A graph is bipartite exactly when it has no cycle of odd length. A triangle (3 nodes in a loop) can never be split: the third node is next to both of the other two, which are on different sides.

An everyday example

Seating guests who don't get along

You are seating wedding guests at two tables, and some pairs must not sit together. Seat one guest at table A. Everyone who clashes with them goes to table B. Everyone who clashes with those goes to table A, and so on. If you ever have to put two clashing guests at the same table, two tables are not enough.

How the example maps to the code
In the exampleIn the code
The two tablesside values 0 and 1
A pair that clashesAn edge [a, b]
A guest not seated yetside[node] === -1
Seating someone at the other tableside[next] = 1 - side[node]
Two clashing guests at one tableside[next] === side[node]

From the slow way to bipartite check (two-coloring)

  1. The slowest way to check for two groups is to try every split. Each node goes in group 0 or group 1, so there are 2^n splits, each checked against every edge. For 30 nodes that is over a billion splits.
  2. But most of those splits don't need to be tried. Once you choose a group for one node, its neighbors have no choice: they must go in the other group. Their neighbors must go back in the first group, and so on. In one connected piece, the first choice decides everything, and the only other answer is the mirror image.
  3. So spread the forced choices with BFS. Give the first node side 0, and give each newly reached node 1 - side[node], the side opposite the node that reached it. Along the way, check every edge: if both ends already have the same side, no split can work.
  4. Separate pieces don't constrain each other, so each one gets its own free first choice. Loop over every node and start a new BFS from each one that has no side yet. That is the bipartite check.

How it works

  1. Build an undirected graph and set every side to -1, meaning not colored yet.
  2. Loop over every node as start. Skip it if it already has a side, because its group was already checked.
  3. Give start side 0 and run a BFS from it with a queue.
  4. For each node taken from the queue, look at each neighbor next.
  5. If next has the same side as node, return false: this edge is inside one group.
  6. If next has no side yet, give it the other side, 1 - side[node], and add it to the queue.
  7. If every group finishes without a clash, return true.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function isBipartite(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [a, b] of edges) {
  4. graph[a].push(b);
  5. graph[b].push(a);
  6. }
  7. const side = new Array(n).fill(-1);
  8. for (let start = 0; start < n; start++) {
  9. if (side[start] !== -1) continue;
  10. side[start] = 0;
  11. const queue = [start];
  12. for (let head = 0; head < queue.length; head++) {
  13. const node = queue[head];
  14. for (const next of graph[node]) {
  15. if (side[next] === side[node]) return false;
  16. if (side[next] === -1) {
  17. side[next] = 1 - side[node];
  18. queue.push(next);
  19. }
  20. }
  21. }
  22. }
  23. return true;
  24. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

Each node is colored and queued once, and each edge is checked from both ends. The adjacency list, side, and the queue fit in O(n + e).

  • Best caseO(n + e)

    Building graph reads every edge. The search itself can stop very early, for example when the first node is part of a triangle.

  • Average caseO(n + e)

    Each node is queued once and each edge is checked from each end until the first clash or the end.

  • Worst caseO(n + e)

    The graph is bipartite, so there is never a clash and every edge is checked from both ends.

Common mistakes

  • Only starting from node 0, so pieces of the graph that 0 can't reach are never checked.
  • Adding each edge in one direction only. Then some clashes are never seen.
  • Checking for a clash only when the neighbor is uncolored. The clash is exactly when it is already colored with the same side.
  • Thinking a graph with any cycle fails. Only odd-length cycles fail; a square is fine.

When to use it

Look for these clues in a problem:

  • The question asks whether things can be split into two groups, teams, colors, or sides.
  • Edges mean "these two must be different" or "these two conflict".
  • The problem mentions two-coloring, or odd loops.
  • It is a matching problem where one side only connects to the other side, such as reviewers and pull requests.

Check yourself

Answer each one in your head first, then open it.

Why do odd cycles break it but even cycles don't?

Going around a cycle, the side flips at every edge. After an even number of flips you are back on the starting side, which matches; after an odd number you are on the other side, which clashes with the start.

Would starting each piece on side 1 instead of 0 change the answer?

No. It just swaps the two groups in that piece. A clash in one coloring is a clash in its mirror image too.

How many times is each edge checked when the graph is bipartite?

Twice, once from each end, because both ends are queued and each reads its full neighbor list.

Is every tree bipartite?

Yes. A tree has no cycles at all, so it has no odd cycles. Putting nodes at even depth on one side and odd depth on the other always works.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

BFS hands out sides by distance. The start gets side 0, and each node reached gets the opposite side of the node that reached it, one step closer. So within a piece, side[x] is the BFS distance from the piece's start, taken mod 2: even distances get 0, odd distances get 1.

If it returns true, the split is valid: every node in every piece was taken from a queue, and each one checked all its neighbors. None had the same side, so every edge joins the two groups.

If it returns false, no split exists. The clash is an edge between u and v whose BFS distances have the same parity. The BFS path from the start to u, the edge, and the BFS path back from v make a closed walk of odd length, and any odd closed walk contains a cycle of odd length. Going around an odd cycle, the sides must alternate an odd number of times and come back changed, which is impossible. So the clash proves no split exists, not just that this one failed. The loops end because each node is colored and queued once.

Going deeper

3 more ideas

Why the forced choices are the only choices

Once you choose a side for start, every node reached from it has no freedom: a neighbor must take the other side, its neighbors must take the first side, and so on. So if this forced coloring hits a clash, no coloring of that group works. Flipping start to side 1 would just flip every color and still clash.

Graphs in several pieces

Each separate piece can be colored on its own, so the outer loop starts a new BFS from every node that isn't colored yet. If you only start from node 0, a triangle in another piece goes unnoticed.

Cost

It is a BFS over the whole graph, so it takes O(n + e) time and O(n + e) memory for the adjacency list, side, and the queue.

Work it by hand

Every step in a table, with why

Two pieces: a 4-node square, and a 4-node square with one extra edge across it.

n = 8, edges = [[0, 3], [3, 5], [5, 1], [1, 0], [2, 4], [4, 6], [6, 7], [7, 2], [2, 6]]

StepstartnodeNeighborssidequeue waitingWhy
10--[0, -1, -1, -1, -1, -1, -1, -1][0]0 has no side yet, so it starts a new piece on side 0.
2003 → 1, 1 → 1[0, 1, -1, 1, -1, -1, -1, -1][3, 1]Both neighbors of 0 are forced to side 1.
3030 ok, 5 → 0[0, 1, -1, 1, -1, 0, -1, -1][1, 5]0 is on the other side from 3, which is fine. 5 is forced to side 0.
4015 ok, 0 oksame[5]Both of 1's neighbors are on side 0, opposite 1. No clash.
5053 ok, 1 oksame[]The square is done: groups {0, 5} and {1, 3}.
61--same-1 already has a side, so the outer loop skips it.
72--[0, 1, 0, 1, -1, 0, -1, -1][2]2 has no side, so it starts the second piece on side 0, its own free choice.
8224 → 1, 7 → 1, 6 → 1[0, 1, 0, 1, 1, 0, 1, 1][4, 7, 6]All three neighbors of 2 are forced to side 1, including 6, because of the extra edge 2-6.
9242 ok, 6 clash[0, 1, 0, 1, 1, 0, 1, 1]-4 and 6 share an edge but both are on side 1. Return false.

It returns false. The edges 2-4, 4-6, and 6-2 form a triangle, a cycle of odd length, which can't be split. The first piece, a square, was fine on its own.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bipartite check (two-coloring)O(n + e)O(n + e)The whole graph is known and you need a yes or no, or the two groups.
Depth-first coloringO(n + e)O(n + e)You prefer recursive code and the graph isn't deep enough to overflow the call stack.
Union-find with sidesO(e · α(n))O(n)Edges arrive one at a time and you need the answer after each one.
Trying every splitO(2^n · e)O(n)Only to check answers in tests with about 15 nodes or fewer.

Extra memory: O(n + e): the adjacency list holds both copies of each edge, and side and queue hold at most n entries.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bipartite check (two-coloring) and the other approaches, on a scale where each line up is 10 times more steps.
  • Bipartite check (two-coloring), Depth-first coloring O(n + e)
  • Union-find with sides O(e · α(n))
  • Trying every split O(2^n · e)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bipartite check (two-coloring)202,0002 million
Depth-first coloring202,0002 million
Union-find with sides101,0001 million
Trying every split10,240more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
No edges: n = 3, edges = []
Every node starts its own piece on side 0 and finds no neighbors. The answer is true.
A self-loop: [3, 3]
graph[3] contains 3, so when 3 is handled, side[3] === side[3] and it returns false. A node that conflicts with itself can't be placed.
An even cycle, such as 6 nodes in a ring
The sides alternate all the way around and match up, so the answer is true.
An odd cycle, such as 5 nodes in a ring
Going around, the last edge joins two nodes on the same side, and the answer is false.
A clash only in a later piece, as in the trace
The outer loop reaches that piece and finds the clash. A version that only starts from node 0 would wrongly return true.

Variations and follow-ups

Twists interviewers add

Depth-first coloring

Use recursion: give a node a side, then call the same function on each neighbor with the other side, returning false on a clash. Same result and cost, with the usual recursion depth limit.

Returning the groups or an odd cycle

On success, the nodes with side 0 and side 1 are the two groups. On failure, keep parent pointers: the two BFS paths to the clashing nodes meet at some node, and together with the clash edge they show an odd cycle as proof.

Union-find with sides

If edges arrive one at a time, keep a union-find where each item also stores whether it is on the same side as its parent. An edge whose two ends are already in one group with the same side is a clash. This answers "is it still two-colorable?" after each edge.

Three or more groups

With 3 groups the question becomes much harder: no fast method is known for every graph, and solutions use backtracking. Two groups is special because each choice forces the next.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "two groups", "two teams", "split so that no two conflicting items are together", or "possible bipartition".
  • Explain the forced choices: "once I place one node, every node in its piece is forced, so one BFS either finds the split or proves there isn't one".
  • Test by hand: a triangle, a square, a self-loop, and two pieces where only the second has an odd cycle.
  • Expect "what about three groups?". Answer: that is a much harder problem with no known fast method in general, so you'd use backtracking on small inputs.

Where frontend code uses it

The same idea in real UI code
  • Scheduling tools that split people or tasks into two shifts or rooms when some pairs can't share one.
  • Matching UIs with two kinds of items, such as reviewers and pull requests or mentors and mentees, where every link goes between the two kinds.
  • Checkerboard-style layouts, such as alternating row colors in a grid of linked cards, where neighbors must always get different colors.

Related algorithms