503. Is Graph Bipartite?
You are handed an undirected graph as an adjacency list graph. There are n nodes labeled 0 to n - 1, and graph[i] lists every node that shares an edge with node i. The list is symmetric (if j appears in graph[i], then i appears in graph[j]), there are no self-loops and no repeated edges, and the graph may be disconnected.
Return true if the nodes can be split into two groups so that every edge joins a node from one group to a node from the other — in other words, if the graph is bipartite. Return false otherwise.
Example 1:
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: Nodes 0, 1, and 2 are pairwise connected — a triangle. Whichever way you split a triangle into two groups, some edge ends up with both endpoints in the same group, so the graph is not bipartite.
Example 2:
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: The graph is a 4-cycle 0–1–2–3–0. Put {0, 2} in one group and {1, 3} in the other: every edge crosses between the groups.
Constraints:
- 1 ≤ n ≤ 100
- 0 ≤ graph[i].length < n
- graph[i] contains no duplicates and never contains i itself
- The list is symmetric: if j is in graph[i], then i is in graph[j]
Hints:
Bipartite means 2-colorable: paint every node red or blue so that no edge connects two nodes of the same color. Think about which structure makes such a painting impossible.
Color any uncolored node, then push colors outward with BFS or DFS — every neighbor must receive the opposite color. If you ever reach a neighbor that already holds the SAME color, you have found an odd cycle: return false. The graph can be disconnected, so restart the coloring from every still-uncolored node.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Expected output: false