Is Graph Bipartite?
Problem Statement
You are given an undirected graph as an adjacency list, where graph[u] contains every vertex adjacent to vertex u. The graph may be disconnected.
Return true if the graph is bipartite: its vertices can be split into two groups such that every edge connects a vertex from one group to a vertex in the other group. Equivalently, the graph is 2-colorable and contains no odd-length cycle.
Input
A 0-indexed adjacency list graph for an undirected graph, possibly with multiple connected components.
Output
A boolean: true if every component can be colored with two colors without an edge inside one color, otherwise false.
Constraints
- •
graph.length == n - •
1 <= n <= 100 - •
0 <= graph[u].length < n - •
0 <= graph[u][i] <= n - 1 - •
graph[u] does not contain u - •
All values in graph[u] are unique - •
If v is in graph[u], then u is in graph[v]
Examples
Example 1
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
falseExample 2
graph = [[1,3],[0,2],[1,3],[0,2]]
trueLearning Objectives
- Translate bipartite testing into a two-color graph traversal problem.
- Detect an odd cycle through a color conflict rather than explicitly searching for cycles.
- Remember to start a traversal from every uncolored vertex because the graph can be disconnected.
Intuition
A bipartite graph is one where every edge crosses between two sides. If you place one vertex on the left side, all of its neighbours must go on the right side. Then their neighbours must go back on the left, and so on. That forced alternation is exactly a BFS or DFS coloring process.
The only way coloring fails is if an edge asks two adjacent vertices to have the same color. That conflict means some path already forced both vertices onto the same side, and the edge between them closes an odd cycle. You do not need to construct the odd cycle; the contradiction is enough.
Disconnected components are the trap. A graph can have several islands of vertices, and an unvisited component has no relationship to colors used elsewhere. Start a fresh coloring traversal from every still-uncolored vertex and treat it as color 0.
Common mistakes
- ×Coloring only from vertex 0 and returning true while another disconnected component contains an odd cycle.
- ×Using a visited boolean without storing colors; visited alone cannot detect same-side edges.
- ×Assigning a neighbour's color but not checking whether an already-colored neighbour conflicts.
- ×Thinking every cycle is invalid. Even cycles are bipartite; odd cycles are the obstruction.
- ×For recursive DFS, forgetting that very large graphs can overflow the call stack, even though this LeetCode constraint is small.
Algorithm Explanation
Use an int array color with -1 meaning uncolored and values 0 or 1 for the two sides. For each vertex, if it is uncolored, start a BFS or DFS and color it 0. Whenever you traverse edge u-v, v must have color 1 - color[u]. If v is uncolored, assign that color and continue. If v is already colored the same as u, return false. If all components finish without conflict, return true.
Solutions
Solution 1: BFS coloring
A safe default because it is iterative and naturally exposes the level-by-level alternation of colors.
For each uncolored component, use a queue to propagate opposite colors along edges. Any edge connecting equal colors proves the graph is not bipartite.
Step-by-step
- Fill color with -1.
- For every uncolored start vertex, color it 0 and enqueue it.
- Pop a vertex; for each neighbour, either assign the opposite color and enqueue it, or detect a conflict if it already has the same color.
- If no component reports a conflict, return true.
O(V + E)
O(V)
Every vertex is colored once and every adjacency-list entry is inspected once.
Java implementation
Solution 2: DFS coloring
Use this when you prefer the compact recursive formulation or when a traversal stack is already part of your template. Mention stack depth if constraints grow.
Recursively demand a color for each vertex. If the vertex was already colored, it is valid only when the existing color matches the demanded color.
Step-by-step
- Iterate through all vertices so disconnected components are included.
- dfs(node, wantedColor) returns false if node already has a different color.
- Otherwise it colors node and recursively asks every neighbour to take the opposite color.
- Any recursive false bubbles up immediately as a global conflict.
O(V + E)
O(V)
The color array is O(V); recursion depth can reach O(V) in a long chain.
Java implementation
Dry Run
Sample input
BFS on graph = [[1,2,3],[0,2],[0,1,3],[0,2]]. The triangle 0-1-2-0 will force a conflict.
| Step | Node popped | Color[node] | Neighbour action | Queue after |
|---|---|---|---|---|
| 1 | 0 | 0 | Color 1, 2, 3 as 1 | [1,2,3] |
| 2 | 1 | 1 | Neighbour 0 is 0, OK; neighbour 2 is 1, conflict | stop |
| 3 | not reached | - | Same-color edge 1-2 proves not bipartite | false |
Vertex 0 forces vertices 1 and 2 to color 1. But 1 and 2 are adjacent, so an edge would stay inside the same side. That contradiction is the odd cycle, and the algorithm returns false.
Interview Tips
Define bipartite in the interview as 2-colorable and immediately connect it to traversal. Then call out disconnected components before writing code. If you choose DFS, mention the recursion trade-off; if you choose BFS, emphasise that levels alternate colors. The correctness proof is simple: every edge enforces opposite colors, and a same-color edge is exactly the contradiction.
Likely follow-ups
- Return the two partitions when the graph is bipartite.
- If the graph is not bipartite, return one odd cycle that proves it.
- Solve Possible Bipartition, where dislikes form the edges.
- Handle a streaming sequence of edges and detect when bipartiteness first breaks.
Similar Problems
Key Takeaways
- Bipartite means every edge crosses between two colors.
- BFS and DFS both work because they propagate forced opposite colors through each component.
- A same-color edge during traversal is an odd-cycle certificate.
- Always loop over every vertex so disconnected components are checked.