DSA problem
Is Graph Bipartite?
There is an undirected graph with n nodes labeled 0 to n - 1, given as an adjacency list graph where graph[u] is the list of nodes adjacent to u. A graph is bipartite if its nodes can be partitioned into two disjoint sets A and B such that every edge connects a node in A to a node in B (no edge lives entirely inside one set). Return true if and only if the graph is bipartite.
Equivalently, a graph is bipartite iff it contains no odd-length cycle. Checking for odd cycles directly is expensive, so we use a much cleaner characterization: a graph is bipartite iff we can 2-color it — assign every node a color in {0, 1} such that no edge has both endpoints the same color.
Run DFS (or BFS) over every connected component, since the graph may be disconnected. Start each component by coloring the seed node 0. When visiting a neighbor: if it is unvisited, color it with the opposite color of the current node and recurse; if it is already colored, verify that its color is opposite to the current node — otherwise an odd cycle exists and we return false immediately.
This 2-coloring DFS visits each node once and each edge twice (undirected), giving O(N + E) time. The color array and recursion stack are O(N) extra space.
Examples
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]falsegraph = [[1,3],[0,2],[1,3],[0,2]]truegraph = [[]]trueConstraints
- graph.length == n
- 1 <= n <= 100
- 0 <= graph[u].length < n
- 0 <= graph[u][i] <= n - 1
- graph[u] does not contain u (no self-loops).
- All the values of graph[u] are unique.
- If graph[u] contains v, then graph[v] contains u (the graph is undirected).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.