Is Graph Bipartite? | February Leetcoding Challenge 2021 | Day 14
logo
Manas Sinha
Developer | Designer

By Manas | 14 February 2021

February LeetCoding Challenge 2021

Day 14

IS GRAPH BIPARTITE?

PROBLEM  STATEMENT:
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.

Explanation

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. It is sometimes also asked as coloring the graph. You have to color every node of the graph with one of two colors such that no two adjacent nodes has same color. ALGORITHM:
  • Algorithm is a modified breadth-first search approach.
  • Maintain a visited array to mark the nodes as visited and a color array to store the color of every node.
  • Iterate over N nodes and do BFS on every non visted node. We are doing this to generalize the solution for disconnected graph.
  • Add the not visited node to the queue, mark it as visited and set its color opposite to its parent node.
  • If the node is visited and its color is same as its parent node return false. Else continue.
  • Finally return true if the graph follows the biaprtite property.

code

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        
        int N = graph.size();
        vector<bool> vis(N,false);
        vector<int> color(N,-1);
        
        for(int k=0;k<N;++k){
        if(vis[k]) continue;
            
        queue<int> q;
        q.push(k);
        
        color[k] = 0;
        vis[k] = true;
        while(!q.empty()){
            int i = q.front();
            q.pop();
            for(int j=0;j<graph[i].size();++j){
                if(!vis[graph[i][j]]){
                    q.push(graph[i][j]);
                    color[graph[i][j]] = color[i] ? 0 : 1;
                    vis[graph[i][j]] = true;
                }
                else{
                    if(color[graph[i][j]] == color[i])
                        return false;
                }
            }
        }
        }
       
        return true;
    }
};

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply