There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:
graph[u] does not contain u).graph[u] does not contain duplicate values).v is in graph[u], then u is in graph[v] (the graph is undirected).u and v such that there is no path between them.A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
Return true if and only if it is bipartite.
Example 1:
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] Output: false Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.
Example 2:
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.
Constraints:
graph.length == n1 <= n <= 1000 <= graph[u].length < n0 <= graph[u][i] <= n - 1graph[u] does not contain u.graph[u] are unique.graph[u] contains v, then graph[v] contains u.Problem Overview: You are given an undirected graph represented as an adjacency list. The task is to determine whether the graph is bipartite. A graph is bipartite if its nodes can be divided into two groups such that no edge connects nodes within the same group. In practice, this means you should be able to color the graph using only two colors so that every edge connects nodes with different colors.
Approach 1: Two-Coloring using BFS (O(V + E) time, O(V) space)
This approach treats the problem as a graph coloring task. Maintain a color array where each node is assigned either 0 or 1. Iterate through every node because the graph may have multiple disconnected components. For each uncolored node, start a BFS traversal and assign it a color. When visiting neighbors, assign the opposite color (1 - color[current]). If you ever encounter a neighbor already colored with the same color as the current node, the graph is not bipartite. BFS works well because it naturally processes nodes level by level, which aligns with alternating colors between adjacent nodes. This method relies on standard graph traversal using a queue and is commonly implemented with Breadth-First Search over an adjacency list.
Approach 2: DFS Coloring (O(V + E) time, O(V) space)
The DFS solution uses the same two-color idea but applies it recursively. Start from an uncolored node, assign a color, then recursively explore its neighbors using Depth-First Search. Each recursive call attempts to color the neighbor with the opposite color. If a conflict occurs (a neighbor already has the same color), immediately return false and propagate the failure up the recursion stack. DFS tends to produce slightly shorter code and works well when recursion depth is manageable. The underlying insight remains identical: adjacent vertices must always have opposite colors.
Alternative Idea: Union-Find Perspective
A less common approach models the constraint using Union Find. For each node, all of its neighbors must belong to the opposite partition. You can union all neighbors of a node together and check that none share the same root as the node itself. While theoretically valid, this implementation is less intuitive than graph coloring and rarely the first choice during interviews.
Recommended for interviews: Use the BFS or DFS two-coloring solution. Interviewers expect you to recognize the bipartite property as a graph coloring problem. Explaining the idea of alternating colors across edges demonstrates strong understanding of graph traversal. BFS is often preferred because it avoids recursion depth issues, while DFS is equally acceptable and slightly more concise.
This approach uses breadth-first search (BFS) to try and color the graph using two colors, validating its bipartiteness. By starting at any unvisited node and attempting to color it with one color, you color all its neighbors with an alternating color. If at any point a neighbor is found to already have the same color, then the graph cannot be bipartite.
This implementation uses a function bfsCheck to perform a BFS from a specific node, attempting to color nodes with two colors. The visited nodes are stored in a queue, and adjacent nodes get an alternating color. The function immediately returns false if any adjacent nodes have the same color, indicating a non-bipartite graph.
The time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as each edge and vertex is visited once in BFS. The space complexity is O(V) due to the storage needed for the color array and the BFS queue.
The depth-first search (DFS) approach is an alternative to BFS for examining bipartiteness. You use DFS recursively to color the graph and check for conflicts. The method still involves checking whether adjacent nodes have opposing colors, iterating through components one by one as needed.
In this C implementation, the dfsCheck function initiates a depth-first recursive coloring, verifying that no adjacent nodes share the same color. Each time a recursive call finds a color conflict, it will return false, propagating back through the recusrsion stack to the caller.
The time complexity is O(V + E), and the space complexity is O(V) due to recursive depth stack space utilization.
Traverse all nodes for coloring. For example, initially color them white, and use DFS to color the adjacent nodes with another color. If the target color to be colored is different from the color that the node has already been colored, it means that it cannot form a bipartite graph.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.
For this problem, if it is a bipartite graph, then all adjacent nodes of each vertex in the graph should belong to the same set and not be in the same set as the vertex. Therefore, we can use the union-find method. Traverse each vertex in the graph, and if it is found that the current vertex and its corresponding adjacent nodes are in the same set, it means that it is not a bipartite graph. Otherwise, merge the adjacent nodes of the current node.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of nodes.
| Approach | Complexity |
|---|---|
| Two-Coloring/BFS Approach | The time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as each edge and vertex is visited once in BFS. The space complexity is O(V) due to the storage needed for the color array and the BFS queue. |
| DFS Approach | The time complexity is O(V + E), and the space complexity is O(V) due to recursive depth stack space utilization. |
| Coloring Method to Determine Bipartite Graph | — |
| Union-Find | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Two-Coloring | O(V + E) | O(V) | Standard solution for bipartite checks; iterative and safe for large graphs |
| DFS Coloring | O(V + E) | O(V) | Clean recursive implementation when recursion depth is manageable |
| Union-Find Grouping | O(V + E α(V)) | O(V) | Useful when solving variations involving connectivity or disjoint sets |
Is Graph Bipartite? - Leetcode 785 - Python • NeetCodeIO • 30,336 views views
Watch 9 more video solutions →Practice Is Graph Bipartite? with our built-in code editor and test cases.
Practice on FleetCode