*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #785 (*Medium*): Is Graph Bipartite?

*Description:*

*Given an undirected graph, return true if and only if it is bipartite.*

*Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B, such that every edge in the graph has one node in A and another node in B.*

*The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.*

*Examples:*

Example 1: | |
---|---|

Input: |
graph = [[1,3],[0,2],[1,3],[0,2]] |

Output: |
true |

Explanation: |
We can divide the vertices into two groups: {0, 2} and {1, 3}. |

Visual: |

Example 2: | |
---|---|

Input: |
graph = [[1,2,3],[0,2],[0,1,3],[0,2]] |

Output: |
false |

Explanation: |
We cannot find a way to divide the set of nodes into two independent subsets. |

Visual: |

*Constraints:*

`1 <= graph.length <= 100`

`0 <= graph[i].length < 100`

`0 <= graph[i][j] <= graph.length - 1`

`graph[i][j] != i`

- All the values of
`graph[i]`

are**unique**. - The graph is
**guaranteed**to be**undirected**.

*Idea:*

The easy solution here is just to run a **breadth first search** approach using a **stack** (or **queue**). We can pick a random starting node and assign it to a group. We then need to check each **next** node connected to our current node (**curr**); if it's been assigned to a group and that group is the same as **curr**, then this graph is not bipartite and we should **return false**. If it hasn't been assigned, we should assign it to the opposite group of **curr** and move it onto the stack to check.

But what if the graph is made up of several disconnected sections? In that case, we need to perform the previous step several times, so we'll need to iterate through the entire graph and skip any nodes that have already been assigned in a previous segment.

If we reach the end without error, then we can **return true**.

*Implementation:*

In order to keep track of assignments, we can use a "visited" array (**vis**). In this case, **0** means that this node hasn't been visited, and **1** or **2** are the assigned groups. To quickly assign **next** to the opposite of **curr**, we can use a **bitwise XOR** with **3**.

```
base 10: base 2:
1 ^ 3 = 2 01 ^ 11 = 10
2 ^ 3 = 1 10 ^ 11 = 01
```

*Javascript Code:*

```
var isBipartite = function(graph) {
let len = graph.length, s = [], vis = new Uint8Array(len)
for (let i = 0; i < len; i++) {
if (vis[i]) continue
vis[i] = 1, s.push(i)
while (s.length) {
let curr = s.pop(), edges = graph[curr]
for (let j = 0; j < edges.length; j++) {
let next = edges[j]
if (!vis[next]) vis[next] = vis[curr] ^ 3, s.push(next)
else if (vis[curr] === vis[next]) return false
}
}
}
return true
};
```

*Python Code:*

```
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
glen = len(graph)
s = []
vis = [0] * glen
for i in range(glen):
if vis[i]: continue
vis[i] = 1
s.append(i)
while len(s):
curr = s.pop()
edges = graph[curr]
for next in edges:
if not vis[next]:
vis[next] = vis[curr] ^ 3
s.append(next)
elif vis[curr] == vis[next]:
return False
return True
```

*Java Code:*

```
class Solution {
public boolean isBipartite(int[][] graph) {
int len = graph.length;
Stack<Integer> s = new Stack<Integer>();
int[] vis = new int[len];
for (int i = 0; i < len; i++) {
if (vis[i] > 0) continue;
vis[i] = 1;
s.push(i);
while (s.size() > 0) {
int curr = s.pop();
int[] edges = graph[curr];
for (int next:edges)
if (vis[next] == 0) {
vis[next] = vis[curr] ^ 3;
s.push(next);
} else if (vis[curr] == vis[next]) return false;
}
}
return true;
}
}
```

*C++ Code:*

```
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int len = graph.size();
stack<int> s;
vector<int> vis(len);
for (int i = 0; i < len; i++) {
if (vis[i] > 0) continue;
vis[i] = 1;
s.push(i);
while (s.size() > 0) {
int curr = s.top();
s.pop();
vector<int> edges = graph[curr];
for (int next:edges)
if (vis[next] == 0) {
vis[next] = vis[curr] ^ 3;
s.push(next);
} else if (vis[curr] == vis[next]) return false;
}
}
return true;
}
};
```

## Discussion (0)