Is Graph Bipartite?

The undirected graph has nodes numbered from 0 through n-1. Each list graph[u] contains the neighbors of node u. Decide whether you can assign every node to one of two groups so that each edge has one endpoint in each group. Return true if such an assignment exists, and false otherwise. The graph may have several disconnected components or isolated nodes; all components must satisfy the rule. There are no self-loops or repeated neighbors, and each edge appears in both endpoints' lists.

Example 1:

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

Output: true

Explanation: Place nodes 0 and 2 in one group and node 1 in the other. Both edges cross between the groups, so the graph is bipartite.

Example 2:

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

Output: false

Explanation: These three nodes form a triangle. Nodes 1 and 2 must both be opposite node 0, which puts them in the same group despite the edge between them. No valid assignment exists.

Example 3:

Input: graph = [[],[]]

Output: true

Explanation: Neither node has any neighbors. There are no edges to violate the grouping rule, so the graph is bipartite.

Constraints:

• 1 <= n <= 100
• Each neighbor list contains fewer than n node numbers, all between 0 and n-1.
• A node is never its own neighbor, and each neighbor appears at most once.
• If v is listed in graph[u], then u is listed in graph[v].
• Neighbor lists need not be sorted.