173. Is Graph Bipartite?

Medium · Graph

Given an undirected graph represented as an adjacency list, determine whether the graph is bipartite. A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

The graph is given as an array where `graph[i]` is a list of indices of the vertices adjacent to vertex `i`. The graph may be disconnected.

Examples

Example 1
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: The graph can be bipartitioned into sets {0, 2} and {1, 3}. Vertex 0 connects to 1 and 3 (both in the other set), vertex 1 connects to 0 and 2 (both in the other set), and so on.
Example 2
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: Vertices 0, 1, 2 form a triangle (odd cycle), so the graph cannot be bipartite.

Constraints