Bipartite Graph Test

A Bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with even cycle using two colors. 

For example, see the following graph below :

It is not possible to color a cycle graph with an odd cycle using two colors.

Let's see a Question before jumping to Bipartite graphs and the implementation.

Problem 1 :

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group. 

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Note:

1. 1 <= N <= 2000
2. 0 <= dislikes.length <= 10000
3. 1 <= dislikes[i][j] <= N
4. dislikes[i][0] < dislikes[i][1]
5. There does not exist i != j for which dislikes[i] == dislikes[j].

Solution : 

As we know a person 'x' dislikes another person 'y', so while making a partition or making a team, we should keep in mind that, these type of people should not be together.

So how can we divide or partition the group of people so that, people who dislike each other remains in different groups?

And the idea behind is the Bipartite Graph (also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent).

So Let's see, two methods to solve this question, through which we will automatically understand how we can check a graph is bipartite or not.

Algorithm to check if a graph is Bipartite, using :

• BFS

1. Make an Adjacency list and a Color Array.
2. Make a Queue, push the parent, give color to parent.
3. Traverse the queue, check whether a parent and its neighbour should not have the same color, if they've simply return false.
4. Else return true.

Code in C++ :

class Solution {

public:

vector<int> adj[2001];// declare a adjacency list

int colors[2001]; // declare a array for inserting the colors

bool possibleBipartition(int N, vector<vector<int>>& dislikes)

{

    for(int i=1;i<=N;i++)

colors[i]=0;// making all nodes to be of '0' color

for(auto v : dislikes)

{

adj[v[0]].push_back(v[1]); // connecting u--v

adj[v[1]].push_back(v[0]); // connecting v--u

}

for(int i=1;i<=N;i++)

{

if(colors[i]==0) // node is not colored yet !!

{

queue<int>q;

q.push(i); // pushing into the Queue

colors[i]=1; // coloring the node-->'i' to '1'

             while(!q.empty()) // will check until the queue is empty

{

int f=q.front(); // taking the parent

q.pop(); // poping it

for(int neigh : adj[f]) // will traverse through level ordering

{

if(colors[neigh]==colors[f])

return false; // if parent and its neighbourer

                        //have same color return false

if(colors[neigh]==0) // if not yet colored

{

colors[neigh]=-colors[f]; // coloring it with just opposite

                            // sign of parent

q.push(neigh);// pushing it into the queue

}

}

}

}

}

return true;

}

};

• DFS

1. Use a color[] array which stores 0 or 1 for every node which denotes opposite colors.
2. Call the function DFS from any node.
3. If the node u has not been visited previously, then assign !color[v] to color[u] and call DFS again to visit nodes connected to u.
4. If at any point, color[u] is equal to !color[v], then the node is bipartite.
5. Modify the DFS function such that it returns a boolean value at the end.

class Solution {

public:

vector<int> adj[2001];// declare a adjacency list

int colors[2001]; // declare a array for inserting the colors

int vis[2001]; // declare a visited array

bool dfs(int v, int c)

{

vis[v]=1; // visiting the node

colors[v]=c; // providing a color-->'c'

for(int child : adj[v]) // going from parent to its children

{

if(!vis[child]) // if not visisted

{

if(dfs(child,c^1)==false) // 'c^1' toggle the value,

//so if parent and child do have same color(c) then return false

return false;

}

else // if visited

{

if(colors[child]==colors[v]) // while back-tracking

//if parent and child have same color(c) then return false

return false;

}

}

return true;

}

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

for(int i=1;i<=N;i++)

colors[i]=0;

for(int i=1;i<=N;i++)

vis[i]=0;

for(auto v : dislikes)

{

adj[v[0]].push_back(v[1]);

adj[v[1]].push_back(v[0]);

}

// if graph is disconneted, then check for individual connected components

for(int i=1;i<=N;i++)

{

if(vis[i]==0 && !dfs(i,0))

return false;

}

return true;

}

};

And this way, we understand how we can traverse a graph either depth-wise or level-wise to check whether the graph is bipartite or not.

Interesting Point in DFS:  

While implementing you will see a case where, if the graph is disconnected, then how you manage to check for bipartite?

Solution : You will run a loop upto 'N' (total number of nodes here) and let's suppose you have three connected components, then you will run your DFS, Thrice.

Code : 

// if graph is disconneted, then check for individual connected components

for(int i=1;i<=N;i++)

{

if(vis[i]==0 && !dfs(i,0))

return false;

}

Problems based on this topic : 

Possible Bipartition