10004 - Bicoloring

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

roy780801
New poster
Posts: 1
Joined: Thu Aug 18, 2011 5:57 am

Re: 10004 - Bicoloring

Post by roy780801 » Thu Aug 18, 2011 7:28 am

Please help me. I have tried many test data and the answers are correct.
but I handed out my program 5 times and got WA 5 times, too.
I don't know where is wrong.

the following are my codes(using C) :

Code: Select all

[code]


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define max 300

int i,j;
int nodenum,edgenum;
int edge_con[max][max];
int color[max];
int r[max];
int ei[max];

struct stack
{
    int b[max];
    int index;   
};

struct stack s;  

void push(int n)
{
    s.b[s.index]=n;
    s.index++;
}

int pop()
{
    s.index--;
    return s.b[s.index];
}

void clear()
{
    s.index=0;
    memset(s.b,-1,sizeof(s.b));
}

int bicolor(int e1)
{
    clear();
    int cur=e1;
    int tar;
    int dcolor=1;
    
    color[cur]=0;
    push(cur);
    while(s.index)
    {
        cur=pop();
        i=0;
        while((tar=edge_con[cur][i])!=-1)
        {
           //printf("cur=%d  tar=%d  i=%d color=%d\n",cur,tar,i,dcolor);
           if(color[tar]==-1)
           {
              color[tar]=dcolor;
              push(tar);
           }
           else if(color[tar]==color[cur])
              return -1;
           i++;
        }
        dcolor=dcolor^1;
    }

    return 0;
}


int main(void)
{
    int e1,e2,ri=0;
    
    while(1)
    {
        memset(edge_con,-1,sizeof(edge_con));
        memset(color,-1,sizeof(color));
        memset(ei,0,sizeof(ei));            
        scanf("%d",&nodenum);
        if(nodenum==0)
          break;
        scanf("%d",&edgenum);
        
        for(i=0;i<edgenum;i++)
        {
            scanf("%d%d",&e1,&e2);
            edge_con[e1][ei[e1]]=e2;
            edge_con[e2][ei[e2]]=e1;
            ei[e1]++;
            ei[e2]++;
        }
        
        r[ri]=bicolor(e1);
        ri++;
        
    }
    
    for(i=0;i<ri;i++)
    {
       if(r[i]==0)
          printf("BICOLORABLE\n");
       else
          printf("NOT BICOLORABLE\n");
    }
    
    system("PAUSE");
    
    return 0;
}








[/code]

rashikh_08
New poster
Posts: 1
Joined: Wed Aug 31, 2011 12:16 am

Re: 10004 - Bicoloring

Post by rashikh_08 » Wed Aug 31, 2011 12:27 am

I dont know what is the problem of this code... I used BFS and tried all the possible test cases and they all gave correct output. But i got WA for several times... :(... anyone could tell me what is the problem of this code???

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
using namespace std;
#define MAX 1000
void bfs(int n,int source);
vector<int>edges[MAX];

int main()
{
int N,E,i,j;

while(scanf("%d",&N))
{
if(N==0)
break;
scanf("%d",&E);
for(i=0;i<E;i++)
{
int x,y;
scanf("%d %d", &x, &y);
edges[x].push_back(y);
edges[y].push_back(x);
}

bfs(N,0);
for(i=0;i<E;i++)
{
edges.clear();
}
}

return 0;
}


void bfs(int n,int source)
{
queue<int>Q;
Q.push(source);
int count=0;
int taken[100]={0};
taken[source]=1;
while(!Q.empty())
{
int u=Q.front();
for(int i=0;i<edges.size();i++)
{
int v=edges;
if(taken[v]==0)
{
if(taken==1)
{
taken[v]=2;
Q.push(v);
}
else if(taken==2)
{
taken[v]=1;
Q.push(v);
}

}
else if(taken[v]==taken)
{
//cout<<taken[v]<<endl;
count++;
}
}
Q.pop();
}
//cout<<"Count: "<<count<<endl;
if(count==0)
cout<<"BICOLORABLE."<<endl;
else
cout<<"NOT BICOLORABLE."<<endl;
//for(int i=0;i<n;i++)
// printf("%d to %d distance %d\n",source,i,distance);
}

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

Re: 10004 - Bicoloring

Post by sadia_atique » Tue Jan 31, 2012 5:39 am

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 :cry: :cry:

Code: Select all

AC
Last edited by sadia_atique on Tue Jan 31, 2012 12:01 pm, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10004 - Bicoloring

Post by sohel » Tue Jan 31, 2012 6:22 am

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
New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

Re: 10004 - Bicoloring

Post by sadia_atique » Tue Jan 31, 2012 8:01 am

Thnax a lot! :D another stupid mistake!

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

Re: 10004 - Bicoloring

Post by anmol_gulati » Mon Feb 04, 2013 12:10 am

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
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10004 - Bicoloring

Post by lbv » Mon Feb 04, 2013 9:04 am

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

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

Code: Select all

NOT BICOLORABLE.
BICOLORABLE.

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

Re: 10004 - Bicoloring

Post by anmol_gulati » Mon Feb 04, 2013 1:59 pm

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

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

10004-Bicoloring

Post by lukai » Mon Feb 11, 2013 10:33 pm

I don't understand why I am getting WA. can anyone help me?

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 100000

vector<int>graph[MAX];
void bfs(int n,int src)
{
    int u,v,loop,temp,soti;
    vector<long long int>v1,v2;
    int taken[200]={0};
    taken[src]=1;
    v1.push_back(src);
    for(loop=1;loop<n;loop++)
    {
        for(int i=0;i<v1.size();i++)
        {
            u=v1[i];
            for(int j=0;j<graph[u].size();j++)
            {
                v=graph[u][j];
                if(!taken[v])
                {
                    taken[v]=1;
                    v2.push_back(v);
                }
            }
        }
        temp=v2[0];
        for(int i=1;i<v2.size();i++)
        {
            for(int j=0;j<graph[temp].size();j++)
            {
                if(v2[i]==graph[temp][j])
                {
                    cout<<"NOT BICOLORABLE."<<endl;
                    soti=1;
                    break;

                }
            }
        }
        if(soti==1)
        {
            break;
        }
        if(v1.empty())
        {
            continue;
        }
        else
        {
            v1.clear();
            v1=v2;
            v2.clear();
        }
        soti=2;
    }
    if(soti==2)
    {
        cout<<"BICOLORABLE."<<endl;
    }

}


int main()
{
    int node,edge,x,y,source;
    while(cin>>node)
    {
        if(node==0)
        {
            return 0;
        }
        cin>>edge;
        for(int i=0;i<edge;i++)
        {
            cin>>x>>y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        bfs(node,x);
        for(int i=0;i<graph[i].size();i++)
        {
            graph[i].clear();
        }
    }

    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10004-Bicoloring

Post by brianfry713 » Wed Feb 13, 2013 12:59 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

Re: 10004-Bicoloring

Post by lukai » Thu Feb 14, 2013 10:49 am

Can you give me some I/O

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10004-Bicoloring

Post by lbv » Thu Feb 14, 2013 5:06 pm

lukai wrote:I don't understand why I am getting WA. can anyone help me?
  • I think you should initialize soti inside the bfs function, or it could be used with a "garbage" value in it, with unpredictable results. Try to configure your compiler to show you all warnings, it can help you catch this type of bugs.
  • When you print "NOT BICOLORABLE.", you break out of one loop, but there's another loop enclosing that code, so it seems there's a chance you end up printing that message more than once for some cases.
You can check these cases:

Code: Select all

4
6
1 0
2 1
3 2
2 0
3 0
1 3

4
3
1 0
2 0
3 2

0

Code: Select all

NOT BICOLORABLE.
BICOLORABLE.

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

Re: 10004-Bicoloring

Post by lukai » Thu Feb 14, 2013 11:26 pm

Thanks brianfry and lbv actually my vector was not cleared properly , so I was getting WA . Now I got AC

Thank you both :)

User avatar
shipu_a
New poster
Posts: 23
Joined: Tue Oct 23, 2012 8:04 pm
Location: Dhaka,Bangladesh
Contact:

Re: 10004-Bicoloring

Post by shipu_a » Mon Mar 04, 2013 12:49 am

Getting WA.........plz help... :oops: :roll:
anyone give me some test case.........plz.... :(

Code: Select all

#include<iostream>
#include<algorithm>
#include<sstream>
#include<fstream>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#define ll long long
#define sc scanf
#define pf printf
#define pi 2*acos(0.0)
using namespace std;
vector<int>ed[100000];
int main()
{

    int n,e,b,s;
    while(sc("%d",&n))
    {
        if(n==0)
        break;
        sc("%d",&e);
        for(int i=0;i<e;i++)
        {
            int x,y;
            cin>>x>>y;
            ed[x].push_back(y);
            ed[y].push_back(x);
        }
        int f=0;
        for(int i=0;i<n;i++)
        {
            int vsize=ed[i].size();
            for(int j=1;j<vsize;j++)
            {
             b=ed[i][j];
             s=ed[b].size();
             for(int k=0;k<s;k++)
             {
                if(ed[b][k]==ed[i][j-1])
                {
                   f=1;
                   break;
                    }
                }
              if(f==1)
              break;
            }
            if(f==1)
             break;
        }
        if(f==1)
        pf("NOT BICOLORABLE.\n");
        else
        pf("BICOLORABLE.\n");
        for(int i=0;i<n;i++)
         ed[i].clear();

    }

    return 0;
}
Nothing is imposible in the world.....And
Never Judge a Book by Its Cover.............
BUBT_Psycho
http://uhunt.felix-halim.net/id/168573
http://shipuahamed.blogspot.com

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10004-Bicoloring

Post by lbv » Mon Mar 04, 2013 3:27 am

shipu_a wrote:Getting WA.........plz help... :oops: :roll:
anyone give me some test case.........plz.... :(
You may try these cases:

Input

Code: Select all

5
5
0 1
1 2
2 3
3 4
4 0
6
6
1 0
2 0
3 2
4 3
5 4
4 1
0
Output

Code: Select all

NOT BICOLORABLE.
NOT BICOLORABLE.

Post Reply

Return to “Volume 100 (10000-10099)”