Bipartite Graph Check

Problem Given an undirected graph, determine whether it is bipartite: can the nodes be 2-colored so that no edge connects two nodes of the same color?

Input / Output

• Input: graph as adjacency list (possibly disconnected).
• Output: boolean.

Constraints

• Up to 10^5 nodes/edges; O(V + E) expected.

Example

• Edges {0-1, 1-2, 2-0} (odd cycle / triangle) → false; a square 0-1-2-3-0 → true.

Expected approach

• BFS or DFS coloring: color a start node 0, neighbors 1, alternating; if an edge ever joins two same-colored nodes, return false. Run from every unvisited node to cover disconnected components. O(V+E) time. Equivalent facts worth stating: bipartite ⇔ no odd-length cycle; Union-Find with "parity" union is an alternative.