Page 5 of 7

Re: 10004 - Bicoloring

Posted: Thu Aug 18, 2011 7:28 am
by roy780801
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]

Re: 10004 - Bicoloring

Posted: Wed Aug 31, 2011 12:27 am
by rashikh_08
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);
}

Re: 10004 - Bicoloring

Posted: Tue Jan 31, 2012 5:39 am
by 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 :cry: :cry:

Code: Select all

AC

Re: 10004 - Bicoloring

Posted: Tue Jan 31, 2012 6:22 am
by 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.

Re: 10004 - Bicoloring

Posted: Tue Jan 31, 2012 8:01 am
by sadia_atique
Thnax a lot! :D another stupid mistake!

Re: 10004 - Bicoloring

Posted: Mon Feb 04, 2013 12:10 am
by 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;
}


Re: 10004 - Bicoloring

Posted: Mon Feb 04, 2013 9:04 am
by lbv
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.

Re: 10004 - Bicoloring

Posted: Mon Feb 04, 2013 1:59 pm
by anmol_gulati
Ohhh Thanx...
How could I have missed this !!!
Anyways, Thanx a lot .

10004-Bicoloring

Posted: Mon Feb 11, 2013 10:33 pm
by lukai
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;
}

Re: 10004-Bicoloring

Posted: Wed Feb 13, 2013 12:59 am
by brianfry713
Doesn't match the sample I/O.

Re: 10004-Bicoloring

Posted: Thu Feb 14, 2013 10:49 am
by lukai
Can you give me some I/O

Re: 10004-Bicoloring

Posted: Thu Feb 14, 2013 5:06 pm
by lbv
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.

Re: 10004-Bicoloring

Posted: Thu Feb 14, 2013 11:26 pm
by lukai
Thanks brianfry and lbv actually my vector was not cleared properly , so I was getting WA . Now I got AC

Thank you both :)

Re: 10004-Bicoloring

Posted: Mon Mar 04, 2013 12:49 am
by shipu_a
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;
}

Re: 10004-Bicoloring

Posted: Mon Mar 04, 2013 3:27 am
by lbv
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.