Bipartite Graph Check

Determine if an undirected graph can be colored with two colors.

graphs bfs coloring validation

Write a function `is_bipartite(n, edges)` that takes the number of vertices `n` (vertices are labeled from `0` to `n-1`) and a list of undirected edges `edges` (each edge is a pair of vertex labels). The graph is guaranteed to be simple: no self-loops and no duplicate edges. The function should return `True` if the graph is bipartite (i.e., its vertices can be partitioned into two independent sets such that every edge connects a vertex in one set to a vertex in the other), and `False` otherwise. The graph may be disconnected, and all vertices must be considered. Implement an efficient solution using BFS or DFS.

Constraints

0 ≤ n ≤ 10^4, 0 ≤ len(edges) ≤ 10^5. Time complexity O(n + m), memory O(n + m).

Example

>>> is_bipartite(4, [(0,1),(1,2),(2,3),(3,0)])
True
>>> is_bipartite(3, [(0,1),(1,2),(2,0)])
False
>>> is_bipartite(1, [])
True
>>> is_bipartite(0, [])
True

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Assign colors 0 and 1 alternately during traversal.

Use an adjacency list to represent the graph.

Start a BFS/DFS from every uncolored vertex to handle disconnected graphs.

If a neighbor has the same color as the current vertex, the graph is not bipartite.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.