C++ Program to Perform Graph Coloring on Bipartite Graphs

Code:

#include    bits/stdc++.h

using namespace std;

int n,e,i,j;
vector > graph;
vector color;
bool vis[100011];

void colour(int node,int num)
{
queue q;
if(vis[node])
return;
color[node]=num;
vis[node]=1;
for(i=0;i
{
if(!vis[graph[node][i]])
{
q.push(graph[node][i]);
}
}
while(!q.empty())
{
colour(q.front(),(num+1)%2);
q.pop();
}
return;
}

int main()
{
int x,y;
cout<<"Enter number of vertices and edges respectively:";
cin>>n>>e;
cout<<"'R' is for Red Colour and 'B' is for Blue Colour.";
cout<<"\n";
graph.resize(n);
color.resize(n);
memset(vis,0,sizeof(vis));
for(i=0;i
{
cout<<"\nEnter edge vertices of edge "<
cin>>x>>y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
colour(0,1);
for(i=0;i
{
if(color[i])
cout<
else
cout<
}
}


Output:

Case 1:
Enter number of vertices and edges respectively:6 5
'R' is for Red Colour and 'B' is for Blue Colour.

Enter edge vertices of edge 1 :1 2

Enter edge vertices of edge 2 :1 3

Enter edge vertices of edge 3 :4 5

Enter edge vertices of edge 4 :4 6

Enter edge vertices of edge 5 :2 4
1 R
2 B
3 B
4 R
5 B
6 B


Case 2:
Enter number of vertices and edges respectively:4 4
'R' is for Red Colour and 'B' is for Blue Colour.

Enter edge vertices of edge 1 :1 2

Enter edge vertices of edge 2 :2 3

Enter edge vertices of edge 3 :3 4

Enter edge vertices of edge 4 :1 4
1 1
2 0
3 1
4 0



More C++ Programs: