Bipartite Graph Check

Given an undirected graph as an adjacency list, determine whether it is **bipartite** — i.e., whether its vertices can be split into two sets such that every edge connects a vertex in one set to a vertex in the other.

Examples

Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

Can be 2-colored: {0,2} and {1,3}.

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Contains an odd cycle, so it's not bipartite.

Constraints

• 1 <= vertices <= 2000
• Graph may be disconnected

Complexity Analysis

Time

O(V + E)

Space

O(V)

color array.

Test Cases

#1 — Bipartite square graph

Input: graph=[[1,3],[0,2],[1,3],[0,2]]

Expected: true

#2 — Odd cycle present

Input: graph=[[1,2,3],[0,2],[0,1,3],[0,2]]

Expected: false

#3 — Single edge

Input: graph=[[1],[0]]

Expected: true

Interactive graph explorer available!

Switch to the Visualize tab to build a custom graph and animate BFS traversal to test your intuition.