Abstract / Summary

Check if a graph can be divided into two groups so no two nodes in the same group are directly connected.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (1+ million submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph Theory
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether an undirected graph is bipartite by attempting to partition its vertices into two disjoint sets, a and b, such that every edge connects a vertex from one set to a vertex from the other. The algorithm proceeds with a depth-first style traversal, expands from a starting vertex, and automatically restarts from an unvisited vertex when the graph consists of multiple disconnected components. A conflict is detected when a vertex would have to belong to both sets, causing an immediate return of False. If the traversal finishes without conflict, the function returns True.

Initialization

At the beginning the algorithm creates two empty collections to represent the two color classes. Set a is seeded with vertex 0, while set b starts empty. A stack named todo holds vertices whose adjacency lists still need to be explored, and a set done records vertices that have already been processed.

a = set([0])
b = set()
todo = [0]
done = set()

Seeding with vertex 0 ensures that the first component is explored immediately. The use of Python’s built-in set type gives constant-time membership checks, which is crucial for the later conflict detection.

Main Traversal Loop

The core of the algorithm is a while loop that runs as long as there are vertices awaiting processing in todo. Each iteration removes the last element from todo, mimicking a stack and thus producing a depth-first order.

while todo:
    i = todo.pop()
    if i not in done:
        done.add(i)
        for g in graph[i]:
            if i in a:
                b.add(g)
            else:
                a.add(g)
            if g in a and g in b:
                return False
            todo.append(g)

Inside the loop the algorithm first checks whether the current vertex i has already been visited. If not, it marks i as visited by adding it to done. Then it iterates over all neighbors g of i. The neighbor is placed into the opposite set of i: if i resides in a, the neighbor is added to b; otherwise it is added to a. After the insertion, a conflict test verifies that the neighbor does not simultaneously belong to both sets. Encountering such a situation means the graph cannot be bipartite, and the function returns False immediately. Finally, each neighbor is pushed onto todo so that its own adjacency list will be examined later.

The conflict test

if g in a and g in b:
    return False

captures the essential property of bipartite graphs: a vertex must be assigned a unique color. By checking both sets after each insertion, the algorithm catches contradictions as soon as they appear, avoiding unnecessary further traversal.

Seed Selection for Disconnected Components

When todo becomes empty, the current component has been fully explored. The algorithm then looks for any vertex that has not yet been visited. If such a vertex exists, it is added to set a and placed onto todo to start a new traversal from that component.

if not todo:
    for i in range(len(graph)):
        if i not in done:
            a.add(i)
            todo.append(i)
            break

This step guarantees that graphs consisting of several isolated subgraphs are handled correctly. By seeding each new component with a fresh vertex in set a, the algorithm preserves the bipartite property across components without mixing colors between them.

Termination Condition

If the outer while loop finishes without triggering the conflict return, every vertex has been visited and no contradictions were found. The function then returns True, indicating that a valid bipartition exists for the entire graph.

return True

Edge Cases Handled

The algorithm gracefully manages several edge conditions:

• Disconnected graphs: The seed selection logic ensures that each isolated component receives its own traversal, preventing premature termination.
• Single-vertex components: A vertex with no neighbors is added to set a and marked as done; the loop proceeds without error.
• Self-loops: If a vertex appears in its own adjacency list, the neighbor insertion will attempt to place the vertex into the opposite set, immediately causing the conflict test to fire and return False, which aligns with the definition that a graph with a self-loop cannot be bipartite.
• Multiple edges between the same pair of vertices: Repeated insertion of the same neighbor does not affect correctness because set membership checks are idempotent; the conflict test still correctly identifies any inconsistency.

Performance Optimizations

The implementation incorporates several choices that improve runtime efficiency:

• Set-based membership: Using set for a, b, and done provides O(1) average-case checks for whether a vertex belongs to a particular color class or has already been processed.
• Early exit on conflict: The moment a vertex would belong to both sets, the function returns False without further exploring the remaining graph, saving work on non-bipartite inputs.
• Stack-style traversal: By treating todo as a stack (pop from the end and append new vertices), the algorithm avoids the overhead of queue management while still guaranteeing that every reachable vertex is eventually examined.
• Minimal re-initialization: The sets a and b persist across components, eliminating the need to recreate them for each disconnected subgraph. Only the seed vertex is added to a for a new component, preserving the existing partitioning information.

These design decisions collectively ensure that the algorithm scales well with the size of the input graph while maintaining clear and direct logic for bipartite verification.

Imagine drawing a big map filled with dots and lines that connect the dots to each other. This code acts like a helper who wants to color every dot either red or blue, but there is one special rule. The rule is that if two dots are connected by a line, they cannot have the same color. One must be red and the other must be blue.

First, the code picks a starting dot and paints it red. Then it looks at all the dots connected to that red dot and paints them blue. After that, it looks at the dots connected to those blue dots and paints them red again. It keeps bouncing back and forth like a game of tag, changing the colors as it moves through the map.

Sometimes, a map has secret tunnels that jump to a different group of dots that are not connected to the first ones. Whenever the code finishes painting one patch of dots, it scans the whole map to see if any dots were left colorless. If it finds one, it picks it up and starts the painting game all over again for that new group.

As it goes along, it keeps a careful eye out for trouble. If the code ever realizes that a dot needs to be exactly red and exactly blue at the same time, it knows that the map is just too tricky to color following those rules. If it gets through every dot without any arguments about colors, then the puzzle is solved.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java		TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python			Rust	Java	Go	TS
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	everthis			JS
	fengvyi	C++
	fpdjsns	C++
	halfrost							Go
	JoshCrozier			JS
	lkwq007		Python
	ruoru					Rust
	shreymehul				C#
	suxrobGM				C#
	trung-hn		Python
	vthwang						Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality