Is Graph Bipartite? solution and explanation
Google
9 more videos on this problem
Is Graph Bipartite? - Leetcode 785 - PythonNeetCodeIO · 11:17 · 31K views
Is Graph Bipartite? | Live Coding with Explanation | Leetcode #785Algorithms Made Easy · 15:41 · 11K views
LeetCode 785. Is Graph Bipartite Explanation and Solutionhappygirlzt · 5:25 · 5K views
LeetCode 785 | Is Graph Bipartite? | Solution Explained (Whiteboard + Algorithm in Java)Xavier Elon · 10:56 · 2K views
[Java] Leetcode 785. Is Graph Bipartite [Search #6]Eric Programming · 12:37 · 2K views
LEETCODE 785 (JAVASCRIPT) | IS GRAPH BIPARTITEAndy Gala · 14:16 · 1K views
785. Is Graph Bipartite? | GRAPHS | | LeetCode Daily Challenge POTDDeep Tech · 20:03 · 561 views
Leetcode 785 - Is Graph Bipartite | C++ DFS SolutionFarjee Guruji · 8:04 · 505 views
Daily Leetcode #759: Apr 29, 2022 - 785. Is Graph Bipartite?Programming Live with Larry · 14:46 · 315 views
Daily Leetcode #320: Feb 14, 2021 - 785. Is Graph Bipartite?Programming Live with Larry · 15:10 · 269 views
The problem
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 containu). - There are no parallel edges (
graph[u]does not contain duplicate values). - If
vis ingraph[u], thenuis ingraph[v](the graph is undirected). - The graph may not be connected, meaning there may be two nodes
uandvsuch 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 containu.- All the values of
graph[u]are unique. - If
graph[u]containsv, thengraph[v]containsu.
Approach overview
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.
Approach 1: Two-Coloring/BFS Approach
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.
from collections import deque
def bfsCheck(start, graph, colors):
queue = deque([start])
colors[start] = 0
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if colors[neighbor] == -1: # Not colored
colors[neighbor] = 1 - colors[node]
queue.append(neighbor)
elif colors[neighbor] == colors[node]:
return False
return True
def isBipartite(graph):
n = len(graph)
colors = [-1] * n
for i in range(n):
if colors[i] == -1:
if not bfsCheck(i, graph, colors):
return False
return True
# Example usage:
graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
print(isBipartite(graph))import java.util.*;
public class BipartiteCheck {
public boolean bfsCheck(int node, int[][] graph, int[] colors) {
Queue<Integer> queue = new LinkedList<>();
queue.add(node);
colors[node] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (colors[v] == -1) {
colors[v] = 1 - colors[u];
queue.add(v);
} else if (colors[v] == colors[u]) {
return false;
}
}
}
return true;
}
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
Arrays.fill(colors, -1);
for (int i = 0; i < n; i++) {
if (colors[i] == -1) {
if (!bfsCheck(i, graph, colors)) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
BipartiteCheck check = new BipartiteCheck();
int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
System.out.println(check.isBipartite(graph));
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool bfsCheck(int start, vector<vector<int>>& graph, vector<int>& colors) {
queue<int> q;
q.push(start);
colors[start] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : graph[node]) {
if (colors[neighbor] == -1) {
colors[neighbor] = 1 - colors[node];
q.push(neighbor);
} else if (colors[neighbor] == colors[node]) {
return false;
}
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> colors(n, -1);
for (int i = 0; i < n; ++i) {
if (colors[i] == -1) {
if (!bfsCheck(i, graph, colors)) {
return false;
}
}
}
return true;
}
int main() {
vector<vector<int>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
cout << (isBipartite(graph) ? "true" : "false") << endl;
return 0;
}function bfsCheck(start, graph, colors) {
let queue = [start];
colors[start] = 0;
while (queue.length > 0) {
let node = queue.shift();
for (let neighbor of graph[node]) {
if (colors[neighbor] === -1) {
colors[neighbor] = 1 - colors[node];
queue.push(neighbor);
} else if (colors[neighbor] === colors[node]) {
return false;
}
}
}
return true;
}
function isBipartite(graph) {
let n = graph.length;
let colors = Array(n).fill(-1);
for (let i = 0; i < n; i++) {
if (colors[i] === -1) {
if (!bfsCheck(i, graph, colors)) {
return false;
}
}
}
return true;
}
// Example usage:
let graph = [[1, 3], [0, 2], [1, 3], [0, 2]];
console.log(isBipartite(graph));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool bfsCheck(int node, int graph[][100], int graphSize, int* graphColSize, int* color) {
int queue[100], front = 0, rear = 0;
queue[rear++] = node;
color[node] = 0;
while (front < rear) {
int u = queue[front++];
for (int i = 0; i < graphColSize[u]; i++) {
int v = graph[u][i];
if (color[v] == -1) { // If not colored, color with opposite color
color[v] = 1 - color[u];
queue[rear++] = v;
} else if (color[v] == color[u]) {
return false;
}
}
}
return true;
}
bool isBipartite(int graph[][100], int graphSize, int* graphColSize) {
int color[100];
memset(color, -1, sizeof(color));
for (int i = 0; i < graphSize; i++) {
if (color[i] == -1) {
if (!bfsCheck(i, graph, graphSize, graphColSize, color)) {
return false;
}
}
}
return true;
}
int main() {
int graph[4][100] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
int graphSize = 4;
int graphColSize[] = {2, 2, 2, 2};
printf("%s\n", isBipartite(graph, graphSize, graphColSize) ? "true" : "false");
return 0;
}using System;
using System.Collections.Generic;
public class BipartiteGraph {
public bool BfsCheck(int start, int[][] graph, int[] colors) {
Queue<int> queue = new Queue<int>();
queue.Enqueue(start);
colors[start] = 0;
while (queue.Count > 0) {
int u = queue.Dequeue();
foreach (int v in graph[u]) {
if (colors[v] == -1) {
colors[v] = 1 - colors[u];
queue.Enqueue(v);
} else if (colors[v] == colors[u]) {
return false;
}
}
}
return true;
}
public bool IsBipartite(int[][] graph) {
int n = graph.Length;
int[] colors = new int[n];
Array.Fill(colors, -1);
for (int i = 0; i < n; i++) {
if (colors[i] == -1) {
if (!BfsCheck(i, graph, colors)) {
return false;
}
}
}
return true;
}
public static void Main() {
BipartiteGraph bg = new BipartiteGraph();
int[][] graph = new int[][] {
new int[] {1, 3}, new int[] {0, 2},
new int[] {1, 3}, new int[] {0, 2}
};
Console.WriteLine(bg.IsBipartite(graph));
}
}The Python version employs BFS checking with the collections.deque structure for efficient queue operations. Nodes are colored sequentially, and any contradiction in coloring through adjacent vertices leads to a false result.
The time complexity is O(V + E), and the space complexity is O(V), mainly due to the array and deque used.
Approach 2: DFS Approach
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.
def dfsCheck(node, color, graph, colors):
colors[node] = color
for neighbor in graph[node]:
if colors[neighbor] == -1:
if not dfsCheck(neighbor, 1 - color, graph, colors):
return False
elif colors[neighbor] == colors[node]:
return False
return True
def isBipartite(graph):
n = len(graph)
colors = [-1] * n
for i in range(n):
if colors[i] == -1:
if not dfsCheck(i, 0, graph, colors):
return False
return True
# Example usage:
graph = [[1,3], [0,2], [1,3], [0,2]]
print(isBipartite(graph))import java.util.*;
public class BipartiteGraphDFS {
public boolean dfsCheck(int node, int color, int[][] graph, int[] colors) {
colors[node] = color;
for (int neighbor : graph[node]) {
if (colors[neighbor] == -1) {
if (!dfsCheck(neighbor, 1 - color, graph, colors)) return false;
} else if (colors[neighbor] == colors[node]) {
return false;
}
}
return true;
}
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
Arrays.fill(colors, -1);
for (int i = 0; i < n; i++) {
if (colors[i] == -1) {
if (!dfsCheck(i, 0, graph, colors)) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
BipartiteGraphDFS bg = new BipartiteGraphDFS();
int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
System.out.println(bg.isBipartite(graph));
}
}#include <iostream>
#include <vector>
using namespace std;
bool dfsCheck(int node, int c, vector<vector<int>>& graph, vector<int>& colors) {
colors[node] = c;
for (int neighbor : graph[node]) {
if (colors[neighbor] == -1) {
if (!dfsCheck(neighbor, 1 - c, graph, colors)) return false;
} else if (colors[neighbor] == colors[node]) {
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> colors(n, -1);
for (int i = 0; i < n; ++i) {
if (colors[i] == -1) {
if (!dfsCheck(i, 0, graph, colors)) {
return false;
}
}
}
return true;
}
int main() {
vector<vector<int>> graph = {{1,3}, {0,2}, {1,3}, {0,2}};
cout << (isBipartite(graph) ? "true" : "false") << endl;
return 0;
}function dfsCheck(node, color, graph, colors) {
colors[node] = color;
for (let neighbor of graph[node]) {
if (colors[neighbor] === -1) {
if (!dfsCheck(neighbor, 1 - color, graph, colors)) {
return false;
}
} else if (colors[neighbor] === colors[node]) {
return false;
}
}
return true;
}
function isBipartite(graph) {
let n = graph.length;
let colors = Array(n).fill(-1);
for (let i = 0; i < n; i++) {
if (colors[i] === -1) {
if (!dfsCheck(i, 0, graph, colors)) {
return false;
}
}
}
return true;
}
// Example usage:
let graph = [[1,3], [0,2], [1,3], [0,2]];
console.log(isBipartite(graph));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool dfsCheck(int node, int c, int graph[][100], int graphSize, int* graphColSize, int* color) {
color[node] = c;
for (int i = 0; i < graphColSize[node]; i++) {
int neighbor = graph[node][i];
if (color[neighbor] == -1) {
if (!dfsCheck(neighbor, 1 - c, graph, graphSize, graphColSize, color)) return false;
} else if (color[neighbor] == color[node]) {
return false;
}
}
return true;
}
bool isBipartite(int graph[][100], int graphSize, int* graphColSize) {
int color[100];
memset(color, -1, sizeof(color));
for (int i = 0; i < graphSize; i++) {
if (color[i] == -1) {
if (!dfsCheck(i, 0, graph, graphSize, graphColSize, color)) {
return false;
}
}
}
return true;
}
int main() {
int graph[4][100] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
int graphSize = 4;
int graphColSize[] = {2, 2, 2, 2};
printf("%s\n", isBipartite(graph, graphSize, graphColSize) ? "true" : "false");
return 0;
}using System;
public class BipartiteGraphDFS {
public bool DfsCheck(int node, int color, int[][] graph, int[] colors) {
colors[node] = color;
foreach (int neighbor in graph[node]) {
if (colors[neighbor] == -1) {
if (!DfsCheck(neighbor, 1 - color, graph, colors)) return false;
} else if (colors[neighbor] == colors[node]) {
return false;
}
}
return true;
}
public bool IsBipartite(int[][] graph) {
int n = graph.Length;
int[] colors = new int[n];
Array.Fill(colors, -1);
for (int i = 0; i < n; i++) {
if (colors[i] == -1) {
if (!DfsCheck(i, 0, graph, colors)) {
return false;
}
}
}
return true;
}
public static void Main() {
BipartiteGraphDFS bg = new BipartiteGraphDFS();
int[][] graph = new int[][] {
new int[] {1, 3}, new int[] {0, 2},
new int[] {1, 3}, new int[] {0, 2}
};
Console.WriteLine(bg.IsBipartite(graph));
}
}In Python, the recursive DFS function dfsCheck checks for coloring conflicts via backtracking as it explores the graph. It responds effectively to earlier function stack calls when an adjacency invalidates a previous assumption.
Achieving a time complexity of O(V + E) with space concerns amounting to O(V) due to recursive depth resolution.
Approach 3: Coloring Method to Determine Bipartite Graph
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.
function isBipartite(graph: number[][]): boolean {
const n = graph.length;
const color: number[] = Array(n).fill(0);
const dfs = (a: number, c: number): boolean => {
color[a] = c;
for (const b of graph[a]) {
if (color[b] === c || (color[b] === 0 && !dfs(b, -c))) {
return false;
}
}
return true;
};
for (let i = 0; i < n; i++) {
if (color[i] === 0 && !dfs(i, 1)) {
return false;
}
}
return true;
}func isBipartite(graph [][]int) bool {
n := len(graph)
color := make([]int, n)
var dfs func(int, int) bool
dfs = func(a, c int) bool {
color[a] = c
for _, b := range graph[a] {
if color[b] == c || (color[b] == 0 && !dfs(b, -c)) {
return false
}
}
return true
}
for i := range graph {
if color[i] == 0 && !dfs(i, 1) {
return false
}
}
return true
}impl Solution {
pub fn is_bipartite(graph: Vec<Vec<i32>>) -> bool {
let n = graph.len();
let mut color = vec![0; n];
fn dfs(a: usize, c: i32, graph: &Vec<Vec<i32>>, color: &mut Vec<i32>) -> bool {
color[a] = c;
for &b in &graph[a] {
if color[b as usize] == c
|| (color[b as usize] == 0 && !dfs(b as usize, -c, graph, color))
{
return false;
}
}
true
}
for i in 0..n {
if color[i] == 0 && !dfs(i, 1, &graph, &mut color) {
return false;
}
}
true
}
}Approach 4: Union-Find
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.
function isBipartite(graph: number[][]): boolean {
const n = graph.length;
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (x !== p[x]) {
p[x] = find(p[x]);
}
return p[x];
};
for (let a = 0; a < n; ++a) {
for (const b of graph[a]) {
const [pa, pb] = [find(a), find(b)];
if (pa === pb) {
return false;
}
p[pb] = find(graph[a][0]);
}
}
return true;
}func isBipartite(graph [][]int) bool {
n := len(graph)
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for a, bs := range graph {
for _, b := range bs {
pa, pb := find(a), find(b)
if pa == pb {
return false
}
p[pb] = find(bs[0])
}
}
return true
}impl Solution {
pub fn is_bipartite(graph: Vec<Vec<i32>>) -> bool {
let n = graph.len();
let mut p: Vec<usize> = (0..n).collect();
fn find(x: usize, p: &mut Vec<usize>) -> usize {
if p[x] != x {
p[x] = find(p[x], p);
}
p[x]
}
for a in 0..n {
for &b in &graph[a] {
let pa = find(a, &mut p);
let pb = find(b as usize, &mut p);
if pa == pb {
return false;
}
p[pb] = find(graph[a][0] as usize, &mut p);
}
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Coloring/BFS Approach | The time complexity is O(V + E), and the space complexity is O(V), mainly due to the array and deque used. |
| DFS Approach | Achieving a time complexity of O(V + E) with space concerns amounting to O(V) due to recursive depth resolution. |
| Coloring Method to Determine Bipartite Graph | – |
| Union-Find | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Is Graph Bipartite? easy or hard?
Is Graph Bipartite? is generally considered a medium-level graph problem. The key challenge is recognizing that the bipartite property can be checked using two-color graph traversal with BFS or DFS. Once that insight is clear, the implementation is straightforward.
Is Graph Bipartite? Python/Java solution
Python and Java solutions typically implement BFS or DFS with a color array. Each node is assigned either 0 or 1, and neighbors receive the opposite color during traversal. If a neighbor already has the same color, the graph is not bipartite. Both implementations run in O(V + E) time.
How to solve Is Graph Bipartite? in O(n)?
Treat the graph as a coloring problem. Use BFS or DFS to assign alternating colors to adjacent nodes while traversing the graph. Each node is processed once and every edge is checked once, giving O(V + E) complexity, which is linear relative to the graph size.
What is the best approach for Is Graph Bipartite??
The best approach is two-color graph traversal using BFS or DFS. Assign one of two colors to each node and ensure that every edge connects nodes with different colors. If a conflict occurs, the graph is not bipartite. Both BFS and DFS solutions run in O(V + E) time with O(V) space.
Is Is Graph Bipartite? asked at Google/Amazon/Meta?
Graph bipartite checking is a classic interview problem that appears frequently in companies like Google, Amazon, Meta, and Microsoft. It tests understanding of graph traversal, adjacency lists, and the concept of graph coloring using BFS or DFS.
What data structure is used in Is Graph Bipartite??
The problem uses an adjacency list to represent the graph and an array to store node colors. BFS implementations rely on a queue, while DFS implementations use recursion or an explicit stack. Some alternative solutions also use the Union-Find data structure for grouping nodes.
What is the time complexity of Is Graph Bipartite??
The optimal solutions using BFS or DFS traverse each vertex and edge at most once. This results in O(V + E) time complexity, where V is the number of vertices and E is the number of edges. Space complexity is O(V) for storing colors and traversal structures like a queue or recursion stack.