Bipartite Graph Code

 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";

}

Post a Comment

0 Comments