Bipartite Graph

#include<bits/stdc++.h>

#define White 1

#define Black 2

#define a graph

#define c color

#define N 1000

using namespace std;

int node, edge, a[N][N], c[N];

bool check(int start)

{

c[start] =White;

queue<int>q;

q.push(start);

while(!q.empty())

{

int x = q.front();

q.pop();

if(a[x][x] == 1)

return false;

for(int i=1;i<=node;i++)

{

if(a[x][i] == 1 && c[i] == 0)

{

if(c[x] == White)

c[i] = Black;

else if(c[x] == Black)

c[i] = White;

q.push(i);

}

if(a[x][i] == 1 && c[x] == c[i])

return false;

}

}

return true;

}

bool Bipartite()

{

for(int i=1;i<=node;i++)

{

if(c[i] == 0)

{

if(check(i) == false)

return false;

}

}

return true;

}

int main()

{

cout << "Enter Node Number :: ";

cin >> node;

cout << "Enter Edge Number :: ";

cin >> edge;

int n1, n2;

cout << "Enter Edge :: \n";

for(int i=1;i<=edge;i++)

{

cin >> n1 >> n2;

a[n1][n2] = 1;

a[n2][n1] = 1;

}

if(Bipartite() == true)

cout << "\nYES Given Graph is Bipartite." << "\n";

else

cout << "\nNO Given Graph is not Bipartite." << "\n";

return 0;

}