Is Graph Bipartite?
Medium · Graphs · Depth-First Search · Breadth-First Search · Union Find · Graph
Problem
You are given an undirected graph with n nodes numbered 0 to n - 1, as an adjacency list: graph[u] lists the neighbors of node u. There are no self-loops and no repeated edges, every edge appears in both directions, and the graph may be split into several pieces.
The graph is bipartite if its nodes can be split into two groups so that every edge joins a node of one group to a node of the other.
Return true if the graph is bipartite, and false otherwise.
Examples
Input: graph = [[1,3],[0,2],[1,3],[0,2]] Output: true
Groups {0, 2} and {1, 3} work: around the 4-cycle the groups alternate.
Input: graph = [[1,2],[0,2],[0,1]] Output: false
Nodes 0 and 1 must differ, and node 2 must differ from both, which two groups cannot do.
Input: graph = [[],[2],[1]] Output: true
Node 0 has no edges and fits in either group; 1 and 2 go in different groups.
Constraints
- n == len(graph)
- 1 <= n <= 100
- 0 <= len(graph[u]) < n
- graph[u] does not contain u and has no repeats
- If v is in graph[u], then u is in graph[v]
Approaches
- Recolor from every node — time O(V · (V + E)), space O(V)
Follow-up
A graph is bipartite exactly when it has no cycle of odd length, which is why a triangle fails and every tree passes. The same two-coloring splits people who dislike each other into two teams, and a union-find version works when edges arrive one at a time: keep, for each node, its parity relative to the root of its set, and an edge between two nodes of the same set and the same parity closes an odd cycle.
Related problems
Start free on Cariara · Coding problems · System design studio
