Bipartite Graph Code
#include<bits/stdc++.h>
using namespace std;
bool dfs_helper(vector<int>graph[], int node, int* visited,int color,int parent){
visited[node]=color;
for(auto nbr:graph[node]){
if(visited[nbr]==0){
int subProb=dfs_helper(graph,nbr,visited,(3-color),node);
if(!subProb)return false;
}
else if(nbr!=parent && color==visited[nbr]){
return false;
}
}
return true;
}
bool dfs(vector<int>graph[],int n){
int visited[n]={0};//0 not visited 1- visited color is 1 2- visited color 2
int color=1;
int ans=dfs_helper(graph,1,visited,color,-1);
for (int i = 1; i < n; i++)
{
cout<<i<<" Color-> "<<visited[i]<<endl;
}
return ans;
}
int main(){
int n,m;
cin>>n>>m;
vector<int>graph[n];
while(m--){
int x,y;
cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
if(dfs(graph,n))cout<<"YES\n";
else cout<<"NO\n";
// cout<<"N";
}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.