Bipartite Graph (DFS)

Hard

Two-colour the graph; a clash means not bipartite

Problem

Return whether a graph is bipartite (2-colorable so no edge joins same-colored nodes).

In simple words

Try 2-colouring with DFS; if two neighbours ever need the same colour, it isn't bipartite.

The idea

A graph is bipartite when its nodes split into two groups with every edge crossing between them. Try to prove it by 2-colouring: paint a start node colour 0, and every neighbour the opposite colour, spreading outward. If you ever reach a node that already wears the same colour as the one you came from, no valid split exists. Even cycles are bipartite; odd cycles are not.

The trick

Each edge forces opposite colours, so a same-colour clash means an odd cycle — which can never be 2-coloured.
Colour spreads like BFS/DFS; disconnected pieces each start their own colouring.

←→stepspaceplay

1/8

Optimal

timeO(V+E)spaceO(V)

1colour[start] = 02queue = [start]3while queue not empty: u = pop4  for each neighbour v: if uncoloured → colour[v] = colour[u] ^ 15                        else if colour[v] == colour[u] → NOT bipartite6no clash anywhere → bipartite (two groups)

Input

nodes: 6, 6 edges

Memory

group B: —

Output

group A: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: graph = [[1,3],[0,2],[1,3],[0,2]]
Output:: true
Explanation:: Nodes split into two clean groups.

Example 2

Input:: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output:: false
Explanation:: An odd cycle breaks 2-colouring → false.

Example 3

Input:: graph = [[1],[0]]
Output:: true
Explanation:: Two nodes, two colours.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.