Bipartite Graph Validation

Given an undirected graph with n nodes labeled 0 to n - 1, represented as an adjacency list graph, determine whether the graph is bipartite — that is, whether its nodes can be split into two sets such that every edge connects a node in one set to a node in the other (equivalently, whether the graph can be properly colored with two colors so that no two adjacent nodes share a color).

The graph may be disconnected, so you must check every component.

Example 1

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

Output: false — node 0 connects to 1, 2, and 3; but 1 and 3 both connect to 2, forcing a triangle-like conflict (0-1-2-0 is an odd cycle through nodes 0,1,2).

Example 2

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

Output: true — nodes {0, 2} can be one color and {1, 3} the other.

Constraints

• graph.length == n, 1 <= n <= 100
• graph[u] is a list of the neighbors of node u; no self-loops or duplicate edges.
• The graph may be disconnected.