Is Graph Bipartite? LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple ByteDance eBay Facebook Google LinkedIn Snapchat Uber
Depth First Search GraphViews 2597

Problem Statement

Is Graph Bipartite LeetCode Solution- 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 the set A and a node in the set B.

Return true if and only if it is bipartite.

Is Graph Bipartite? LeetCode Solution

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.

Is Graph Bipartite? LeetCode Solution

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

Approach:

A bipartite graph (or digraph) is a graph whose vertices can be divided into two disjoint and independent sets, that is every edge connects a vertex into one. Vertex sets and. are usually called the parts of the graph. This problem can be easily understood and solved by assuming that each node is a graph that can be colored blue(1), red(0), or none(-1). If after traversal we found even a single node has a different color then the graph is not a bipartite graph. Here we are using the fact that in a bipartite graph no 2 adjacent nodes will be colored with the same color (1 or 0 for example)

We will initialize a list of colors with 0 (by default). Next, we will assign each node with color, either: 1 or -1. Remember that in the bipartite graph, no two adjacent nodes can have the same color.
If we caught two adjacent nodes with the same color, we will return false immediately.

Code:

Is Graph Bipartite? C++ Leetcode Solution:

class Solution {
private:
    bool checkIfBipartite(int current, vector<vector<int>> &graph, vector<int> &color) {
        if(color[current] == -1)
            color[current] = 1;
        for(auto it : graph[current]) {
            if(color[it] == -1) {
                color[it] = 1 - color[current];
                if(!checkIfBipartite(it, graph, color))
                    return false;
            } else if(color[it] == color[current])
                return false;
        }
        return true;
    }
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, -1);
        for(int i = 0; i < n; ++i) {
            if(!checkIfBipartite(i, graph, color))
                return false;
        }
        return true;
    }
};

Is Graph Bipartite? Java Leetcode Solution:

class Solution {
    private static boolean checkBipartite(int current, int[][] graph, int[] color) {
        if(color[current] == -1)
            color[current] = 1;
        for(int adj : graph[current]) {
            if(color[adj] == -1) {
                color[adj] = 1 - color[current];
                if(checkBipartite(adj, graph, color) == false)
                    return false;
            } else if(color[adj] == color[current]) 
                return false;
        }
        return true;
    }
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int color[] = new int[n];
        for(int i = 0; i < n; ++i) 
            color[i] = -1;
        for(int i = 0; i < n; ++i) {
            if(checkBipartite(i, graph, color) == false)
                return false;
        }
        return true;
    }
}

Complexity Analysis for Is Graph Bipartite Leetcode Solution:

Time Complexity

O(V+E) for doing the standard DFS approach.

Space Complexity

O(V) for storing the colors array and the auxiliary space required for recursion.

Translate »