bipartite graph in discrete mathematics
Bipartite Graph-
A bipartite graph is a special kind of graph with the following properties-
It consists of two sets of vertices X and Y.
The vertices of set X join only with the vertices of set Y.
The vertices within the same set do not join.bipartite graph
//Bipartite Graph (BFS)/ Graph coloring
//Do check striver graph series
#include<bits/stdc++.h>
using namespace std;
void addedge(vector<int>adj[],int u,int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
bool bfsbipar(int source_node,vector<int>adj[],int color[])
{
queue<int>q;
q.push(source_node);
color[source_node]=0;
while(!q.empty())
{
int f=q.front();
q.pop();
for(auto i:adj[f])
{
if(color[i]==-1)
{
if(color[f]==1)
{
color[i]=0;
}
else
{
color[i]=1;
}
q.push(i);
}
else if(color[i]==color[f])
{
return false;
}
}
}
return true;
}
bool checkbipar(vector<int>adj[],int n)
{
int color[n];
for(int i=0;i<n;i++)
{
color[i]=-1;
}
for(int i=0;i<n;i++)
{
if(color[i]==-1)
{
if(!bfsbipar(i,adj,color))
{
return false;
}
}
}
return true;
}
int main()
{
int n,v;
cout<<"Enter the number of vertex, edges: ";
cin>>n>>v;
int a,b;
vector<int>adj[n];
cout<<"enter the link:"<<endl;
for(int i=0;i<v;i++)
{
cin>>a>>b;
addedge(adj,a,b);
}
if(checkbipar(adj,n))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
return 0;
}Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
