Implementation of bipartite graph using c++

 What a bipartite graph:-

 A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.

Code:-

here we take a colour array in which we store the colour in form of 1 and 0 .if colour of parent and child is same then the graph is not a bipartite graph.

in the  code I use c^1 (c xor 1) that means if c have 1 then after xor operation it become 0 and if 0 then it become 1  

// Bipartite graph

#include<bits/stdc++.h>

using namespace std;

vector<int> arr[100];

int visited[100];

// array for colour

int col[100];

// function for dfs

bool dfs(int v,int c)

{

visited[v]=1;

col[v]=c;

for(int child:arr[v])

{

if(visited[child]==0)

{

auto f=dfs(child,c^1);

if(f==false)

{

return false;

}

}

else

{

if(col[v]==col[child])

return false;

}

}

return true;

}

//Driver function

int main()

{

int n,m;

printf("Enter number vertex and number of edges\n");

cin>>n>>m;

int a,b;

cout<<"Enter all the edges"<<endl;

for(int i=0;i<m;i++)

{

cin>>a>>b;

arr[a].push_back(b);

arr[b].push_back(a);

}

auto c=dfs(1,1);

if(c==false)

cout<<"Not a Bipartite graph";

else

cout<<"Bipartite graph";

return 0;

}

Output:-

for the graph

since is a bipartite graph. so let's check by the code

Enter the number of vertex and edges

6 6

Enter all edges

1 2

1 6

2 3

3 4

4 5

5 6

Bipartite graph