In this guide, you will get 785. Is Graph Bipartite? LeetCode Solution with the best time and space complexity. The solution to Is Graph Bipartite? problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V|)
785. Is Graph Bipartite? LeetCode Solution in C++
enum class Color { kWhite, kRed, kGreen };
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
vector<Color> colors(graph.size(), Color::kWhite);
for (int i = 0; i < graph.size(); ++i) {
// This node has been colored, so do nothing.
if (colors[i] != Color::kWhite)
continue;
// Always paint red for a white node.
colors[i] = Color::kRed;
// BFS.
queue<int> q{{i}};
while (!q.empty())
for (int sz = q.size(); sz > 0; --sz) {
const int u = q.front();
q.pop();
for (const int v : graph[u]) {
if (colors[v] == colors[u])
return false;
if (colors[v] == Color::kWhite) {
colors[v] =
colors[u] == Color::kRed ? Color::kGreen : Color::kRed;
q.push(v);
}
}
}
}
return true;
}
}; /* code provided by PROGIEZ */
785. Is Graph Bipartite? LeetCode Solution in Java
enum Color { kWhite, kRed, kGreen }
class Solution {
public boolean isBipartite(int[][] graph) {
Color[] colors = new Color[graph.length];
Arrays.fill(colors, Color.kWhite);
for (int i = 0; i < graph.length; ++i) {
// This node has been colored, so do nothing.
if (colors[i] != Color.kWhite)
continue;
// Always paint red for a white node.
colors[i] = Color.kRed;
// BFS.
Queue<Integer> q = new ArrayDeque<>(List.of(i));
while (!q.isEmpty())
for (int sz = q.size(); sz > 0; --sz) {
final int u = q.poll();
for (final int v : graph[u]) {
if (colors[v] == colors[u])
return false;
if (colors[v] == Color.kWhite) {
colors[v] = colors[u] == Color.kRed ? Color.kGreen : Color.kRed;
q.offer(v);
}
}
}
}
return true;
}
} // code provided by PROGIEZ
785. Is Graph Bipartite? LeetCode Solution in Python
from enum import Enum
class Color(Enum):
kWhite = 0
kRed = 1
kGreen = 2
class Solution:
def isBipartite(self, graph: list[list[int]]) -> bool:
colors = [Color.kWhite] * len(graph)
for i in range(len(graph)):
# This node has been colored, so do nothing.
if colors[i] != Color.kWhite:
continue
# Always paint red for a white node.
colors[i] = Color.kRed
# BFS.
q = collections.deque([i])
while q:
for _ in range(len(q)):
u = q.popleft()
for v in graph[u]:
if colors[v] == colors[u]:
return False
if colors[v] == Color.kWhite:
colors[v] = Color.kRed if colors[u] == Color.kGreen else Color.kGreen
q.append(v)
return True # code by PROGIEZ
