In this post, we are going to solve the 785. Is Graph Bipartite? problem of Leetcode. This problem 785. Is Graph Bipartite? is a Leetcode medium level problem. Let’s see the code, 785. Is Graph Bipartite? – Leetcode Solution.
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== 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, thengraph[v]contains u.
Now, let’s see the code of 785. Is Graph Bipartite? – Leetcode Solution.
Is Graph Bipartite? – Leetcode Solution
We are going to solve the problem using Graph Data structure and will solve this problem using both BFS – Breadth First Search traversal as well DFS – Depth First Search Traversal. Let’s see the solution.
Using BFS traversal
First, we are going to see the solution to this problem using the BFS traversal of Graph.
785. Is Graph Bipartite? – Solution in Java
class Solution {
public boolean findBipartite(int i, int[][] graph,int[] color){
Queue<Integer> q = new LinkedList<>();
q.add(i);
color[i] = 1;
while(!q.isEmpty()){
int node = q.poll();
for(int e : graph[node]){
if(color[e] == -1){
color[e] = 1 - color[node];
q.add(e);
} else if(color[e] == color[node]){
return false;
}
}
}
return true;
}
public boolean isBipartite(int[][] graph) {
int[] color = new int[graph.length];
for(int i=0;i<graph.length;i++) color[i] = -1;
for(int i=0; i<graph.length ;i++){
if(color[i] == -1){
if(!findBipartite(i,graph,color)) return false;
}
}
return true;
}
}
785. Is Graph Bipartite? – Solution in C++
class Solution {
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> color(n); // 0: uncolored; 1: color A; -1: color B
queue<int> q;
for (int i = 0; i < n; i++) {
if (color[i]) continue;
color[i] = 1;
for (q.push(i); !q.empty(); q.pop()) {
int cur = q.front();
for (int neighbor : graph[cur])
{
if (!color[neighbor])
{ color[neighbor] = -color[cur]; q.push(neighbor); }
else if (color[neighbor] == color[cur])
return false;
}
}
}
return true;
}
}
785. Is Graph Bipartite? – Solution in Python
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
n, colored = len(graph), {}
for i in range(n):
if i not in colored and graph[i]:
colored[i] = 1
q = collections.deque([i])
while q:
cur = q.popleft()
for nb in graph[cur]:
if nb not in colored:
colored[nb] = -colored[cur]
q.append(nb)
elif colored[nb] == colored[cur]:
return False
return True
These were the solution to the problem, 785. Is Graph Bipartite? – Leetcode Solution using the BFS traversal on graph approach. Now, we are going to solve this problem using the DFS traversal approach.
Using DFS traversal
First, we are going to see the solution to this problem using the DFS traversal of Graph.
785. Is Graph Bipartite? – Solution in Java
class Solution {
public boolean findBipartite(int i, int[][] graph,int[] color){
if(color[i] == -1) color[i] = 1;
for(int e : graph[i]){
if(color[e] == -1){
color[e] = 1 - color[i];
if(!findBipartite(e,graph,color)) return false;
} else if(color[e] != -1){
if(color[e] == color[i]) return false;
}
}
return true;
}
public boolean isBipartite(int[][] graph) {
int[] color = new int[graph.length];
for(int i=0;i<graph.length;i++) color[i] = -1;
for(int i=0; i<graph.length ;i++){
if(color[i] == -1){
if(!findBipartite(i,graph,color)) return false;
}
}
return true;
}
}
785. Is Graph Bipartite? – Solution in C++
class Solution {
public:
vector<int>vis,col;
bool dfs(int v, int c, vector<vector<int>>& graph){
vis[v]=1;
col[v]=c;
for(int child:graph[v]){
if(vis[child]==0){
// here c^1 is for flipping 1 by 0 or 0 by 1, that is flip the current color
if(dfs(child,c^1,graph)==false)
return false;
}
else{
if(col[v]==col[child])
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n=graph.size();
vis.resize(n);
col.resize(n);
for(int i=0;i<n;++i){
if(vis[i]==0 && dfs(i,0,graph)==false){
return false;
}
}
return true;
}
};
785. Is Graph Bipartite? – Solution in Python
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
n, colored = len(graph), {}
def dfs_color(color, idx, graph, colored):
if idx in colored:
return color == colored[idx]
colored[idx] = color
return all(dfs_color(-color, nb, graph, colored) for nb in graph[idx])
return all(i in colored or dfs_color(1, i, graph, colored) for i in range(n))
These were the solution to problem 785. Is Graph Bipartite? – Leetcode solution using the DFS traversal on graph approach.
Note: This problem 785. Is Graph Bipartite? – Leetcode solution is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.