**Write a C++ Program to Perform Graph Coloring on Bipartite Graphs**

**Program:**

#include<bits/stdc++.h>

using
namespace std;

int n,e,i,j;

vector<vector<int>
> graph;

vector<int>
color;

bool
vis[100011];

void
colour(int node,int num)

{

queue<int>
q;

if(vis[node])

return;

color[node]=num;

vis[node]=1;

for(i=0;i<n;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<e;i++)

{

cout<<"\nEnter
edge vertices of edge "<<i+1<<" :";

cin>>x>>y;

x--; y--;

graph[x].push_back(y);

graph[y].push_back(x);

}

colour(0,1);

for(i=0;i<n;i++)

{

if(color[i])

cout<<i+1<<"
"<<'R'<<"\n";

else

cout<<i+1<<"
"<<'B'<<"\n";

}

}

**Output:**

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

## No comments:

## Post a Comment