Is Graph Bipartite

Given an undirected graph, determine whether it can be colored using two colors so that no edge connects nodes of the same color. Pattern focus: Bipartite check. Traverse the graph component by component and enforce alternating colors.

Input Format

graph = adjacency list of an undirected graph

Output Format

true if the graph is bipartite

Constraints

  • 1 <= n <= 10^5
  • Graph is undirected and represented as adjacency lists.

Examples

Example 1:

Input:

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

Output:

true

Explanation:

This 4-cycle is bipartite.

Example 2:

Input:

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

Output:

false

Explanation:

An odd cycle exists, so the graph is not bipartite.

Example 3:

Input:

graph = [[]]

Output:

true

Explanation:

A single isolated node is bipartite.

Loading...
Is Graph Bipartite - Graph Traversal DSA Problem