Is Graph Bipartite?

Med

#0739Time: O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is checked once across all DFS calls.Space: O(V), where V is the number of vertices. This space is used for the `colors` array and the recursion call stack. In the worst-case scenario of a path graph, the recursion depth can be up to V.2 companies

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Graph

Companies

Samsung Pinterest

Prompt

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:

There are no self-edges (graph[u] does not contain u).
There are no parallel edges (graph[u] does not contain duplicate values).
If v is in graph[u], then u is in graph[v] (the graph is undirected).
The graph may not be connected, meaning there may be two nodes 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 == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] does not contain u.
All the values of graph[u] are unique.
If graph[u] contains v, then graph[v] contains u.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a recursive Depth-First Search (DFS) traversal to check for bipartiteness. The core idea is to assign one of two colors (e.g., 1 and -1) to each node. We start from an arbitrary uncolored node, assign it the first color, and then traverse its neighbors. Each neighbor is assigned the opposite color. If we encounter a neighbor that is already colored with the same color as the current node, we have found an odd-length cycle, which means the graph is not bipartite. Since the graph might be disconnected, we iterate through all nodes to ensure every component is checked.

Algorithm

Initialize a colors array of size n with 0s (representing uncolored nodes).
Iterate through each node i from 0 to n-1.
If node i is uncolored (colors[i] == 0), it means we have found a new, unvisited component of the graph.
Start a recursive Depth-First Search (DFS) from this node. Call a helper function, e.g., dfs(graph, colors, i, 1), assigning it an initial color (e.g., 1).
If the dfs call ever returns false, it means a conflict was found in that component, so the graph is not bipartite. Return false immediately.
The dfs(node, color) helper function:
- Assign the given color to the current node by setting colors[node] = color.
- For each neighbor of the current node:
  - If the neighbor is uncolored (colors[neighbor] == 0), recursively call dfs on it with the opposite color: dfs(graph, colors, neighbor, -color). If this recursive call returns false, propagate the false result up.
  - If the neighbor is already colored, check if its color is the same as the current node's color (colors[neighbor] == color). If it is, a conflict is found, so return false.
If the main loop finishes without any dfs call returning false, it means all components were successfully two-colored. Return true.

Walkthrough

We use an auxiliary array, colors, to store the color of each node. A value of 0 means uncolored, 1 means color A, and -1 means color B. The main function iterates through all nodes. If a node hasn't been colored yet, we start a DFS from it with an initial color (e.g., 1). The recursive DFS function dfs(node, color) works as follows:

Color the current node with the given color.
For each neighbor of the node:
- If the neighbor is uncolored, recursively call dfs(neighbor, -color). If this recursive call returns false, it means a conflict was found deeper in the traversal, so we propagate false up.
- If the neighbor is already colored, check if colors[neighbor] == colors[node]. If they have the same color, it violates the bipartite property, so we return false.
If the loop finishes without finding any conflicts, it means this part of the graph is bipartite, so we return true. If the main loop completes and all components are successfully colored, the entire graph is bipartite.

1class Solution {2    public boolean isBipartite(int[][] graph) {3        int n = graph.length;4        int[] colors = new int[n]; // 0: uncolored, 1: color A, -1: color B5 6        for (int i = 0; i < n; i++) {7            // If the node is not yet colored, start a DFS from it.8            if (colors[i] == 0) {9                if (!dfs(graph, colors, i, 1)) {10                    return false;11                }12            }13        }14        return true;15    }16 17    private boolean dfs(int[][] graph, int[] colors, int node, int color) {18        colors[node] = color;19        for (int neighbor : graph[node]) {20            if (colors[neighbor] == 0) {21                // If neighbor is uncolored, color it with the opposite color and recurse.22                if (!dfs(graph, colors, neighbor, -color)) {23                    return false;24                }25            } else if (colors[neighbor] == color) {26                // If neighbor has the same color, conflict found.27                return false;28            }29        }30        return true;31    }32}

Complexity

Time

O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is checked once across all DFS calls.

Space

O(V), where V is the number of vertices. This space is used for the `colors` array and the recursion call stack. In the worst-case scenario of a path graph, the recursion depth can be up to V.

Trade-offs

Pros

Conceptually straightforward and easy to implement using recursion.
Optimal time complexity for solving this problem.

Cons

The recursive implementation can lead to a StackOverflowError if the graph is very deep (i.e., has a very long path). However, given the constraint n <= 100, this is not a practical concern for this specific problem.

This approach uses an iterative Breadth-First Search (BFS) traversal. Similar to the DFS method, it attempts to color the graph's nodes with two alternating colors. We use a queue to manage the nodes to visit. When we process a node, we color its uncolored neighbors with the opposite color and add them to the queue. If we find a neighbor that is already colored with the same color as the current node, we've detected a conflict (an odd-length cycle), and the graph is not bipartite. This process is repeated for all disconnected components of the graph.

Algorithm

Initialize a colors array of size n with 0s (uncolored).
Iterate through each node i from 0 to n-1.
If node i is uncolored (colors[i] == 0), start a BFS traversal for this component.
- Create a Queue and add i to it.
- Color the starting node i with an initial color, e.g., colors[i] = 1.
- While the queue is not empty:
  - Dequeue a node, let's call it u.
  - For each neighbor v of u:
    - If v is uncolored (colors[v] == 0), color it with the opposite color of u (colors[v] = -colors[u]) and enqueue v.
    - If v is already colored, check if its color is the same as u's (colors[v] == colors[u]). If so, a conflict exists, and the graph is not bipartite. Return false.
If the main loop completes without finding any conflicts, it means all components are bipartite. Return true.

Walkthrough

We maintain a colors array, where 0 indicates an uncolored node, 1 represents color A, and -1 represents color B. We also use a Queue for the BFS traversal. The algorithm iterates through all nodes to handle potentially disconnected graphs. If a node is uncolored, we start a BFS traversal from it:

Assign an initial color (e.g., 1) to the starting node and add it to the queue.
While the queue is not empty, dequeue a node u.
For each neighbor v of u:
- If v is uncolored (colors[v] == 0), assign it the opposite color of u (-colors[u]) and enqueue it.
- If v is already colored and colors[v] == colors[u], it means two adjacent nodes have the same color. This is a conflict, so we return false.
If the BFS for a component completes without any conflicts, we continue the main loop. If the entire loop finishes without returning false, the graph is bipartite.

1import java.util.Queue;2import java.util.LinkedList;3 4class Solution {5    public boolean isBipartite(int[][] graph) {6        int n = graph.length;7        int[] colors = new int[n]; // 0: uncolored, 1: color A, -1: color B8 9        for (int i = 0; i < n; i++) {10            if (colors[i] == 0) { // This node belongs to a component we haven't visited yet11                Queue<Integer> queue = new LinkedList<>();12                queue.add(i);13                colors[i] = 1; // Start coloring with color 114 15                while (!queue.isEmpty()) {16                    int node = queue.poll();17                    for (int neighbor : graph[node]) {18                        if (colors[neighbor] == 0) {19                            // If neighbor is uncolored, color with opposite color and add to queue20                            colors[neighbor] = -colors[node];21                            queue.add(neighbor);22                        } else if (colors[neighbor] == colors[node]) {23                            // If neighbor has the same color, conflict found24                            return false;25                        }26                    }27                }28            }29        }30        return true;31    }32}

Complexity

Time

O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is enqueued and dequeued at most once, and every edge is examined once.

Space

O(V), where V is the number of vertices. This space is required for the `colors` array and the `Queue`. In the worst case, the queue can hold up to O(V) nodes (e.g., in a star graph).

Trade-offs

Pros

Avoids recursion, thus preventing any potential for stack overflow errors, making it more robust for very large or deep graphs.
Optimal time and space complexity.
Often slightly faster in practice than recursive DFS due to lower overhead from function calls.

Cons

The iterative logic using a queue might be slightly more complex to write for some developers compared to the recursive DFS approach.

Solutions

Solution

1class Solution {2private3  int[] color;4private5  int[][] g;6public7  boolean isBipartite(int[][] graph) {8    int n = graph.length;9    color = new int[n];10    g = graph;11    for (int i = 0; i < n; ++i) {12      if (color[i] == 0 && !dfs(i, 1)) {13        return false;14      }15    }16    return true;17  }18private19  boolean dfs(int u, int c) {20    color[u] = c;21    for (int v : g[u]) {22      if (color[v] == 0) {23        if (!dfs(v, 3 - c)) {24          return false;25        }26      } else if (color[v] == c) {27        return false;28      }29    }30    return true;31  }32}

1class Solution {2public:3  bool isBipartite(vector<vector<int>> &graph) {4    int n = graph.size();5    vector<int> color(n);6    for (int i = 0; i < n; ++i)7      if (!color[i] && !dfs(i, 1, color, graph))8        return false;9    return true;10  }11  bool dfs(int u, int c, vector<int> &color, vector<vector<int>> &g) {12    color[u] = c;13    for (int &v : g[u]) {14      if (!color[v]) {15        if (!dfs(v, 3 - c, color, g))16          return false;17      } else if (color[v] == c)18        return false;19    }20    return true;21  }22};

1class Solution:2    def isBipartite(self, graph: List[List[int]]) -> bool: def dfs(u, c): color[u] = c for v in graph[u]: if not color[v]: if not dfs(v, 3 - c): return False elif color[v] == c: return False return True n = len(graph) color = [0] * n for i in range(n): if not color[i] and not dfs(i, 1): return False return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem