## 10004 - Bicoloring

Moderator: Board moderators

### Re: 10004 - Bicoloring

I don't get why I'm getting WA in bicolouring..tried to think about many possible mistakes,tried some sample inputs,but still WA.I used bfs here,started from the 1st input node,coloured it 1,then colored all its adjecent to 2,thus went on..when got some node that its adjacent is same color as it,then bicolor=0 and break loop,print not bicolorable,otherwise bicolorable..don't know what went wrong.Anyone please help
Code: Select all
`AC`
Last edited by sadia_atique on Tue Jan 31, 2012 12:01 pm, edited 1 time in total.
New poster

Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

### Re: 10004 - Bicoloring

The main part of your code is correct. However, you are not reading the input properly.
For this problem, input ends with a 0. What you are doing is reading it till EOF. So, at the very end, when n = 0, you are supposed to break away from the program. But you are printing something before quitting and hence the WA.

You can do something like this to make it work while( scanf("%d",&n) == 1 && n != 0 )

hope it helps.

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### Re: 10004 - Bicoloring

Thnax a lot! another stupid mistake!
New poster

Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

### Re: 10004 - Bicoloring

I cant understand why am I getting a WA here,seems to be an easy problem, I have tried this many times checked manually on many test cases but still getting WA..
I'm doing a BFS here , taking 0th node as source and coloring it 0 , and then checking each adjacent node of parent and if not colored , then coloring it as opposite to that of parent else checking it with parent's color (if same then printing NOT BICOLORABLE.). and then adding it to the queue.

Please see my code here and tell me what am i doing wrong.
Code: Select all
`#include<iostream>#include<stdio.h>#include<queue>#define SIZE 201#define YES -1                      // defines G is NOT BICOLORABLE#define NO -2                      // defines it is still Bicolorableusing namespace std;int main(){    struct graph{int connect;}G[200][200];        int visit[200],color[200];         queue<int> Q;int n,l,i,x,y,check,u,j;while( scanf("%d",&n) == 1 && n != 0 ){            scanf("%d",&l);             for(i=0;i<n;i++)                   // Graph initialisation            {                  color[i] = NO;              // initially all nodes not colored                    visit[i] = NO;                           for(j=0;j<n;j++)                  G[i][j].connect  = NO;            }for(i=0;i<l;i++){scanf("%d %d",&x,&y);G[x][y].connect = YES;G[y][x].connect = YES;}check = NO;color[0] = 0;                              // coloring 0th node as 0Q.push(0);visit[0] = YES;while(Q.size()>0 && check==NO){    u  = Q.front();    Q.pop();            for(i=0;i<n && check==NO ;i++)        if(G[u][i].connect==YES && (u!=i) )         {        if(visit[i]==NO )            {                visit[i] = YES;                 if(color[i]==NO)                 {                 if(color[u]==0)                 color[i] = 1;                 else                 color[i] = 0;}                               Q.push(i);           }         else if(color[i]==color[u])          {           printf("NOT BICOLORABLE.\n");           check = YES;}                // check is basically used to break out of loop      } }if(check == NO)printf("BICOLORABLE.\n");}return 0;}`
anmol_gulati
New poster

Posts: 2
Joined: Sun Feb 03, 2013 11:59 pm

### Re: 10004 - Bicoloring

anmol_gulati wrote:I cant understand why am I getting a WA here,seems to be an easy problem, I have tried this many times checked manually on many test cases but still getting WA..

Make sure you clear your queue at the beginning of each test case, or previous data can affect the results. Check for example:
Code: Select all
`331 02 01 2211 00`

Code: Select all
`NOT BICOLORABLE.BICOLORABLE.`
lbv
Learning poster

Posts: 54
Joined: Tue Nov 29, 2011 8:40 am

### Re: 10004 - Bicoloring

Ohhh Thanx...
How could I have missed this !!!
Anyways, Thanx a lot .
anmol_gulati
New poster

Posts: 2
Joined: Sun Feb 03, 2013 11:59 pm

Previous

### Who is online

Users browsing this forum: No registered users and 1 guest