# Is Graph Bipartite? – Leetcode Solution

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 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.

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? – Solutionin Java

```class Solution {

public boolean findBipartite(int i, int[][] graph,int[] color){
color[i] = 1;

while(!q.isEmpty()){
int node = q.poll();
for(int e : graph[node]){
if(color[e] == -1){
color[e] = 1 - color[node];
} 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? – Solutionin 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.