Solution: Is Graph Bipartite?
Tags: algorithms, javascript, java, leetcode
Published: 2021-02-14 11:15:54

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/is-graph-bipartite/discuss/1065185).*

---

####[Leetcode Problem #785 (*Medium*): Is Graph Bipartite?](https://leetcode.com/problems/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 1 Visual](https://assets.leetcode.com/uploads/2020/10/21/bi1.jpg)

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:*|![Example 2 Visual](https://assets.leetcode.com/uploads/2020/10/21/bi2.jpg)

---

***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**.
```js
     base 10:             base 2:
   1 ^ 3  =  2         01 ^ 11  =  10
   2 ^ 3  =  1         10 ^ 11  =  01
```

---

***Javascript Code:***
```javascript
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:***
```python
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:***
```java
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:***
```c++
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;
    }
};
```