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

**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:falseExplanation: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:trueExplanation: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;
}
};
```