10004 - Bicoloring

[sadia_atique]

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


[sohel]

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.

[sadia_atique]

Thnax a lot! another stupid mistake!

[anmol_gulati]

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 Bicolorable
using 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 0
Q.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;
}



[lbv]

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

3
3
1 0
2 0
1 2
2
1
1 0
0


Code: Select all

NOT BICOLORABLE.
BICOLORABLE.


[anmol_gulati]

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