## 193 Graph Coloring

Moderator: Board moderators

### 193 Graph Coloring

I use the testcase provided by Mr.NightZ-1 in artical "193 WA why? What's wrong in my algorithm??????".
However, I got a strange answer diffenent from the one provided by Mr.sohel in some cases...

ex.

inpunt:
20 19
1 10
2 5
3 4
4 9
5 17
6 4
8 19
9 13
10 11
11 14
12 1
13 6
14 3
15 4
16 5
17 8
18 9
19 15
20 4

Mr.sohel's output:
11
1 2 3 6 7 8 9 11 15 16 20

My output:
11
2 4 7 10 12 13 14 16 17 18 19

The total amount of colored nodes is the same, but the node to be colored is quite diefferent @_@

Other cases are also the same. I always got the same amount of colored nodes but with different selections...

I've drew out the real graph and check my answers. They seem to be correct seems the connected component right next to the colored node are kept "clean".

I've noticed that this problem has different possiilities of answer. However, I always got WA even though my answer seems to be correct , comparing with Mr. sohel's, which have got AC.

Can anyone point out the possible mistake I've made?

Thanks. ^^
anne0604
New poster

Posts: 4
Joined: Tue Aug 08, 2006 10:36 pm

this problem has a correction program.
That means any valid answer will be accepted.
I guess, your code has slight mistake somewhere.

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

I used a Brute Force method . I tried to paint every node BLACK and then tried to find the solution. I did dot get TLE from judge, rather I got WA !!

But my code gave right answers for all the inputs I found. Anyone can help me ??

Code: Select all
#include<stdio.h>
#include<string.h>

#define BLACK 1
#define WHITE 2

bool a[105][105];
int col[105];
int savecol[105];
int blacks,v;

void paint(int index,int c)
{
int i;
if(c==BLACK)
{
blacks++;
}
col[index]=c;
if(c==BLACK)
{
for(i=1;i<=v;i++)
{
if(a[index][i])
{
paint(i,WHITE);
}
}
}
return;
}

int main(void)
{

int t,e,n1,n2,i,j,temp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&v,&e);

memset(a,false,sizeof(a));
memset(col,0,sizeof(col));

for(i=0;i<e;i++)
{
scanf("%d%d",&n1,&n2);
a[n1][n2]=a[n2][n1]=true;
}

int max=0;
for(j=1;j<=v;j++)
{
memset(col,0,sizeof(col));
blacks=0;
paint(j,BLACK);
for(i=1;i<=v;i++)
{
if(col[i]==0)
{
paint(i,BLACK);
}
}
if(blacks>max)
{
max=blacks;
for(i=1;i<=v;i++)
{
savecol[i]=col[i];
}
}
}

printf("%d\n",max);
temp=max;
i=1;
while(temp>1)
{
if(savecol[i]==BLACK)
{
printf("%d ",i);
temp--;
}
i++;
}
while(savecol[i]==WHITE && i<=v)
{
i++;
}
printf("%d\n",i);

}
return 0;
}
[\code]
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Kallol
Learning poster

Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

i didnt code this problem.
but i think the simplest solution would be..

1. run a bfs
2. bicolor the graph
3. check which color has greater value - black or white
4. if its white, define white as black
5. print nblack, and print the vertex those are black

its not very easy to look through other's code and understand whats going on there!
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

smilitude wrote:2. bicolor the graph

That's not always possible.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

its not a bi-colorable problem , because two whites can be adjacent. Any way , is there any tricky input to dodge my code ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Kallol
Learning poster

Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

### Re: 193 Graph Coloring

is it a connected graph?
chengouxuan
New poster

Posts: 10
Joined: Wed Dec 15, 2010 12:32 pm

### Re: 193 Graph Coloring

Hellow Guyssssssssssssssssssssss

it can be solved using back tracking algorithm.

1- check if u have the complete solution that is checking if you have colored all the nodes.
2- if yes, then save the information which are how many black nodes u have and what they are,
3- else, go to the next node and try to color it according to the rule, that it could be always white, but black only if there are no connected black nodes to it., (take all the possible colors for that nodes)
4- pick the first possible color, recur by going to step 1
5- then u should be able to come back to take the other possiblity of colors.

I have solved it and it works OK, but my code takes long time for some test cases, I wanna know WHY!!! and how can I iptimize my solution????

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

void Construct(bool c[], int &nCandidates, int edges, int **edge, int k, bool*a)
{

nCandidates=0;
bool legalblack= true;

for(int i =0; i<edges; i++)
{
if((edge[i][0]== k && a[edge[i][1]]== false ) || (edge[i][1]== k && a[edge[i][0]]== false ))
legalblack = false;

}

c[nCandidates] = true;
nCandidates++;

if(legalblack == true)
{

c[nCandidates] = false;
nCandidates++;
}
}

void back_track(vector<int> counter,vector<vector<int> > seq,int edges,int **edge, int nodes, int k,int index, bool *a, vector<int> &counterO,vector<vector<int> > &seqO, int &X)
{

bool c[2];
int nCandidates;

if(k == nodes)
{

counterO.push_back(counter[index]);

for(int j =0; j <seq[index].size(); j++)
{

seqO[X].push_back(seq[index][j]);

}

X++;

index++;
counter.push_back(0);

}

else{

k++;

Construct(c, nCandidates, edges, edge, k,a);

for(int i =0; i <nCandidates; i++)
{
a[k]= c[i];

if(a[k]== false)
{

counter[index]++;
seq[index].push_back(k);
}

back_track(counter,seq,edges,edge,nodes,k,index,a,counterO, seqO,X);

}
}
}

int main ()
{

int t;
cin>>t;

for(int i =0; i <t; i++)
{

int nodes;
int edges;

cin>>nodes>>edges;

int **edge = new int *[edges];

for(int i =0; i <edges; i++)
edge[i]= new int [2];

for(int i =0; i <edges; i++)
cin>>edge[i][0]>>edge[i][1];

vector<int> counter;
counter.push_back(0);
vector<vector<int> > seq (pow(2.0,double(nodes)));

vector<int> counterO;
vector<vector<int> > seqO(pow(2.0,double(nodes)));

bool *a= new bool[nodes+1];
int X=0;
back_track(counter,seq,edges,edge,nodes,0,0,a,counterO, seqO,X);

int max =0;

for(int i =0; i <counterO.size(); i++)
{
if(counterO[i]>max)
{
max= counterO[i];
}
}

for(int i =0; i <counterO.size(); i++)
{
if(counterO[i]== max)
{
cout<<counterO[i]<<endl;

for(int j =0; j <seqO[i].size(); j++)
cout<<seqO[i][j]<<" ";

cout<<endl;
break;

}
}

}

return 0;
}

//:D
back_tracker
New poster

Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

### Re: 193 Graph Coloring

Kallol, I really liked your code because it's very fast....I think your mistake is that you specify the size "105" for bool a and color. Maybe sometimes it needs more space than that, so maybe it should be moe general. good luck
back_tracker
New poster

Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

### Re: 193 Graph Coloring

Try this Input who are getting WA
Input :
Code: Select all
3

5 0

8 4
1 2
3 4
5 6
6 8

2 1
1 2

Output :
Code: Select all
5
1 2 3 4 5
5
2 4 5 7 8
1
2
@li_kuet
New poster

Posts: 25
Joined: Fri May 25, 2012 6:22 pm

### Re: 193 Graph Coloring

Hi Everyone,

Below is my code for this problem. It uses simple Breadth first search. Moreover, for each node, it tries to color it both white and black(assuming adjacent node is not black). I have no idea why my output in not right. I will be grateful if someone could take a look and tell what is wrong with my code. If you tell me mistake, it will motivate me to solve more problems and becoem better. PLEASE HELP

Code: Select all
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<iostream>
#include<sstream>
using namespace std;
#define INF (1<<30)
class StoreAns{
public:
int count ;
string seq ;
};

StoreAns findMax(queue<int> q, char color[],vector<int> d){

int v = q.front();q.pop();
bool any = false;
for(int i = 0 ; i < adjList[v].size();i++){
if(d[k] == INF){
any = true;
q.push(k);
color[k] = 'w';
d[k] = d[v] + 1;
StoreAns a1 = findMax(q,color,d);
if(color[v] != 'b'){
color[k] = 'b';
StoreAns a2 = findMax(q,color,d);
a2.count  = a2.count + 1;
if(a1.count > a2.count) return a1;
std::stringstream storestringnum;
storestringnum << (k+1);
a2.seq = storestringnum.str()+ " " + a2.seq;
return a2;

}else return a1;

}//end inf chk

}
if(!any) {
StoreAns temp;
temp.count = 0;

temp.seq = "";
return temp;

}

}

StoreAns printMaxBlack(int nn){
d[0] = 0;
char color[105];
queue<int> q; q.push(0); color[0] = 'w';
StoreAns a1 = findMax(q,color,d);
color[0] = 'b';
StoreAns a2 = findMax(q,color,d); a2.count = a2.count+1;
if(a1.count > a2.count) return a1;
std::stringstream storestringnum;
storestringnum << 1;
a2.seq = storestringnum.str() + " " + a2.seq;
return a2;

}

int main(){
//string r = "";
//int num = 100;
//char x[21];
//std::stringstream storestringnum;
//storestringnum << num;
//
//string y = storestringnum.str() + " " + r;
//cout<<"The concat is: " << y;
freopen("in.txt","r",stdin);
for(int i = 0 ; i < 105;i++) adjList.push_back(vector<int>());
int ng,nn,ne,n1,n2;
scanf("%d",&ng);
for(int x = 0 ; x < ng; x++){
scanf("%d %d",&nn,&ne);
for(int i = 0 ; i < nn;i++) adjList[i].clear();
for(int i = 0; i < ne; i++){
scanf("%d %d",&n1,&n2);
}
StoreAns temp = printMaxBlack(nn);
cout<<temp.seq<<endl;

}//end tc for

return 0;

}
hover1178
New poster

Posts: 3
Joined: Mon Jan 21, 2013 11:57 am

### Re: 193 Graph Coloring

@problemsolve I don't know why but I used dfs got WA then tried using backtracking and even though I thought I might get TLE got AC!:)

Can anyone explain why? Specially if you've solved it using BFS or DFS and got AC? Thanks.
AKJ88
New poster

Posts: 17
Joined: Wed Feb 13, 2013 10:48 am