bipartite graph dfs
//Bipartite graph / Graph coloring
//Using DFS(recursion)
#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 bipar(int sr,vector<int>adj[],int color[])
{
if(color[sr]==-1)
{
color[sr]=1;
}
for(auto i:adj[sr])
{
if(color[i]==-1)
{
color[i]=1-color[sr];
if(!bipar(i,adj,color))
{
return false;
}
}
else if(color[i]==color[sr])
{
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(!bipar(i,adj,color))
{
return false;
}
}
}
return true;
}
int main()
{
int n,v;
cout<<"Enter the no. of vertex and edges:";
cin>>n>>v;
vector<int>adj[n];
int a,b;
cout<<"enter the links:"<<endl;
for(int i=0;i<n;i++)
{
cin>>a>>b;
addedge(adj,a,b);
}
if(checkbipar(adj,n))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}