UVA Online Judge Problem 10004 Bicoloring solution in C++

Problem name: 10004 Bicoloring

Platform: UVA Online Judge

Click here to see the problem statement.

 

 

At first, try hard to solve the problem on your own. If you could not solve the problem on your own after trying hard, read my solution idea.

 

 

 

“Bicoloring” Problem Statement Editorial:

In this problem, the nodes are labeled from 0<node<n. Where n is the total number of nodes. They said that we have to color every node by using 2 colors only.

 

Also, we can’t color 2 adjacent nodes using the same color. That is why the problem name is bicoloring.

 

They also mentioned that it is a bidirectional graph. If you can go from node a to b, you can definitely go from node b to a.

 

Our task is to find whether it is possible to color every 2 nodes connected by edge using two different colors.

This is actually required from you to make a program to solve this problem.

 

 

 

 

 

 

 

 

UVA Online Judge Problem “Bicoloring” Solution Idea Applying BFS:

 

First, consider the following cases:

Case-1:

3

3

0 1

1 2

2 3

In this case, as we can easily color two adjacency nodes using different colors so our answer is:

 

BICOLORABLE.

 

 

 

 

 

Case-2:

3

4

0 1

1 3

1 2

3 0

 

In this case, we have at first color node 0 with color a and node 1 with color b. Then as already, we have colored node 1 using color b so we have to color node 3 using color a. But at the last edge where 3 and 0 were connected. We already colored node 0 as a and node 3 as a. So, both of the nodes are colored as a which is not different. So, the answer, in this case, is the graph is:

 

NOT BICOLORABLE

 

This is a straight-cut BFS problem. You can solve this problem using BFS.

 

As we have only 2 colors and we can’t use the same color for every two nodes connected by the edges. So, we have to use order the nodes in only 2 levels.

 

If it is not possible to organize all the nodes in 2 levels then the graph is “NOT BICOLORABLE”. Otherwise, it is “BICOLORABLE”.

 

To accomplish this at first we will make an adjacency list using the nodes connected by each edge. Then we start from any node and put them in two-level.

I have used level 0 and level 1. First I take a node which I have taken input at the last of the adjacency list and make it as my source node and push it into the queue. Also, make that node visited and also level it as 0.

 

 

Now in the BFS loop, our task is to check every node in the every adjacency list in the 2d vector. If the node is not visited we will color it.

 

Consider we are in the a-th list of the vector v[a][b] indicating b is connected to a. And if our a-th node is leveled as 0 then definitely we will level the b-th node as 1 and vice-versa.

 

But in the case when the v[a][b] node is already visited. It indicates that we have colored a and b-th nodes according to another source node.

In this case, if we already colored node a and node b using the same level. Then we can’t color these two nodes using different colors. So, we can’t make this graph Bicolorable.

 

So, we have to check every node of every edge and start coloring them either by 0 or 1. When we are unable to color them using these 2 colors. And both of the nodes are already colored using the same color. We have to exit from the loop and print the answer as NOT BICOLORABLE. Otherwise, it is COLORABLE.

 

 

 

 

Please try to solve this problem on your own now. If you still failed then look at my code.

 

 

 

 

My Code To Solve 10004 Bicoloring UVA Problem:

 

 

 

/* ANTHOR KUMAR DAS

KUET ECE 2K18*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define sc(a) scanf(“%d”,&a)

#define sc1(n) scanf(“%lld”,&n)

#define tc ll tc; sc1(tc);while(tc–)

#define sc2(b,c) scanf(“%lld%lld”,&b,&c)

#define f(a,c,b) for(a=c;a<b;a++)

#define pb(a) push_back(a)

#define pf push_front

#define p(k) printf(“%lldn”,k)

#define pt printf

#define en printf(“n”)

#define br break

#define dot(m) cout<<fixed<<setprecision(10)<<m<<endl

#define co continue

#define sc3(s) scanf(“%s”,&s)

#define ye cout<<“YES”<<endl

#define mp(a,b) make_pair(a,b)

#define mm memset

#define ss second

#define ff first

#define no cout<<“NO”<<endl

#define valid(x,y,row,col) (x>=1&&x<=row&&y>=1&&y<=col)

#define pii pair<ll,ll>

ll fx[]= {0,0,1,-1,1,1,-1,-1};

ll fy[]= {1,-1,0,0,1,-1,1,-1};

int main()

{

ll tt;

 

while(cin>>tt)

{

if(tt==0)

{

br;

}

 

ll a,b,c,k,p,n,m,mn=INT_MAX,mx=INT_MIN,t,j,i,l,z=0;

bool ans=true;

sc1(m);

ll ar[tt];

mm(ar,0,sizeof(ar));

vector<ll>v[tt];

//At first we will make an adjacency list using the edges

f(i,0,m)

{

sc2(a,b);

v[a].pb(b);

v[b].pb(a);

 

}

//Now we will do bfs

//We can take any node as source node let say we are going to take our last inputed node

ll vis[tt];

mm(vis,0,sizeof(vis));

ll lev[tt];

queue<ll>q;

q.push(a);

vis[a]=1;

lev[a]=0;

while(q.size()>0)

{

k=q.front();

q.pop();

f(i,0,v[k].size())

{

p=v[k][i];

if(vis[p]==0)

{

if(lev[k]==0)

{

lev[p]=1;

}

else

{

lev[p]=0;

}

q.push(p);

vis[p]=1;

}

else

{

if(lev[p]==lev[k])

{

ans=false;

br;

}

}

}

}

 

if(ans)

{

printf(“BICOLORABLE.n”);

}

else

{

printf(“NOT BICOLORABLE.n”);

}

 

 

}

return 0;

}

 

 

Thanks for reading the UVA problem 10004 Bicoloring problem solution idea. If you want to get more problems for practice and solution ideas click here.

 

Also, Check my next tutorial’s problem and try to solve this using Breadth First Search Algorithm.