Solution: Is Graph Bipartite?

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;
    }
};

Comments

[Rohith V]

We can solve it using Union Find Template :

class Solution {
    public boolean isBipartite(int[][] graph) {
        int row = graph.length;
        UnionFind uf = new UnionFind(row);
        for (int i=0; i<row; i++) {
            for (int j=0; j<graph[i].length; j++) {
                if (uf.find(i) == uf.find(graph[i][j]))
                    return false;
                uf.union(graph[i][0], graph[i][j]);
            }
        }
        return true;
    }
}

class UnionFind {
    int size;
    int component;
    int [] parent;
    int [] rank;

    public UnionFind(int n) {
        size = n;
        component = n;
        parent = new int [n];
        rank = new int [n];
        for (int i=0; i<n; i++)
            parent[i] = i;
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        if (rank[rootP] < rank[rootQ]) {
            parent[p] = rootQ;
        }
        else {
            parent[q] = rootP;
            if (rank[rootP] == rank[rootQ])
                rank[rootP] += 1;
        }
        component -= 1;
    }
}