aloalgoBipartite Graph Checker
You are given an undirected graph represented as an adjacency list neighbors, where neighbors[i] is an array of integers representing the neighbors of node i.
Your task is to determine if the graph is bipartite. A graph is bipartite if its nodes can be divided into two disjoint sets such that every edge connects a node in one set to a node in the other set.
You may assume that:
- Nodes are numbered from
0toneighbors.length - 1. - The graph may be disconnected.
- There are no self-loops or parallel edges.
Return true if the graph is bipartite, otherwise return false.
Example 1
[ [1, 3], [0, 2], [1, 3], [0, 2] ]
True
The graph is a 4-node cycle (0-1-2-3-0). It can be two-colored: nodes {0, 2} in one set and nodes {1, 3} in the other. Every edge connects nodes from different sets.
Example 2
[ [1, 2], [0, 2], [0, 1] ]
False
The graph is a triangle (0-1-2-0). It contains an odd-length cycle, so it cannot be two-colored. No matter how you assign colors, at least one edge will connect two nodes of the same color.
Example 3
[ [1], [0], [3], [2] ]
True
The graph has two disconnected components: (0-1) and (2-3). Each component is bipartite, so the entire graph is bipartite.
[ [1, 3], [0, 2], [1, 3], [0, 2] ]
True