10004 - Bicoloring

Moderator: Board moderators

Try this case:
Code: Select all
`430 31 22 30`

Its obviously bicolorable.
----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Thank you very much .. Rio !!!
Ron
Learning poster

Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

TLE

HI i am having TLE in this prob, can u plz help?

AC
Eagle er moto daana meley urbo

New poster

Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

Re: 10004 - Bicoloring WA

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

Re: 10004 - Bicoloring

At lastttttttttt GOT ACCEPTED yeyeye:
My Algo:Using like floyd Warshall starting from any first vertex(let A)...color it 1...take all of its adjacent(let B,C) ..(Now i will color all adjacent of A to -1 but i will have to check a condition that after coloring any adjacent of -1 color should not have -1 color)...for that now taking first adjacent(B) check all adjacent of that adjacent(B)..let(D,E) if anyone of D or E has the same color(-1) ..then it means graph is not bicolorable else if all conditions gaot satisfied for all vertex IT is biclorable...
"Accepted" is my passion but RTE is my weakness.....
empo
New poster

Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Re: 10004 - Bicoloring

Below is my code. What is the problem
Code: Select all
`spelling mistake. lol`
asqwzxdfercv
New poster

Posts: 3
Joined: Sat May 16, 2009 3:40 am

Re: 10004 - Bicoloring

Can Sombody help me with my WA!!

Code: Select all
` GoT AC --Dont Forget The dot at the end of your Lines `
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Angeh
Experienced poster

Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10004 - Bicoloring

Code: Select all
`#include<stdio.h>#include<queue>#define  MAX 201using namespace std;queue<int>ans;int n,e;int path[MAX][MAX];int col[MAX];void ini(){   for(int i=0;i<MAX;i++){      for(int j=0;j<MAX;j++)         path[i][j]=0;      col[i]=0;   }}int bfs(int u){   int temp;   ans.push(u);   col[u]=1;   while(!ans.empty()){      temp=ans.front();      ans.pop();      for(int i=0;i<n;i++){         if(path[temp][i]==1){            if(col[i]==0){               ans.push(i);               if(col[temp]==1)                  col[i]=2;               else                  col[i]=1;            }                        else if(col[i]==col[temp])               return 0;                           }      }   }   return 1;}int main(){   freopen("1004.txt","r",stdin);   int a,b,val;   while((scanf("%d",&n)==1)){      if(n==0)         break;      scanf("%d",&e);      ini();      for(int i=0;i<e;i++){         scanf("%d %d",&a,&b);         path[a][b]=path[b][a]=1;      }            if(e>0)      val=bfs(a);      else         val=1;      if(val==0)         printf("NOT BICOLORABLE.\n");      else         printf("BICOLORABLE.\n");            }   return 0;}`
asif_khan_ak_07
New poster

Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 10004 - Bicoloring

" freopen("1004.txt","r",stdin);
int a,b,val;
while((scanf("%d",&n)==1)){
if(n==0)

"

how can it possible
just comment the line like
// freopen("1004.txt","r",stdin)
Try to catch fish rather than asking for some fishes.
arifcsecu
Learning poster

Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong

Re: 10004 - Bicoloring

Just got AC on this problem. Some tips:
1. Don't assume that there will be node 0, so don't start your BFS at node 0, use other trick
2.
Code: Select all
`   Color the starting node ( passed to your BFS func ) with color 1 and enqueue it    for each adjacent node         if not visited already            mark visited                        color it with the opposite of the parent color            enqueue it        else             if parentColor == currentNodeColor               "NOT BICOLORABLE."    "BICOLORABLE."`
valkov
New poster

Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 10004 - Bicoloring

I am asraful .
I tried to solve 10004
But i am getting WA .

Here is my code ...
Code: Select all
`#include<stdio.h>int main(){    int m[203][203],a[203],d[203],p[5],l,e,n,i,j,k;     char c[203];while(scanf("%d",&n) && n){for(i=0;i<203;++i)for(j=0;j<203;++j)   m[i][j]=0;for(i=0;i<203;++i) { a[i]=i; c[i]='Z'; d[i]=0; }for(i=0;i<5;i++) p[i]=0; scanf("%d",&e);for(i=1;i<=e;++i){  scanf("%d%d",&j,&k);  m[j][k]=m[k][j]=1; }for(i=0;i<n;++i){     k=0;for(j=0;j<n;++j)  if(m[i][j]==1)     ++k;     d[i]=k;}for(i=0;i<n-1;++i) for(j=i+1;j<n;++j)    if(d[i]<d[j]){      k=d[i];      d[i]=d[j];      d[j]=k;      k=a[i];      a[i]=a[j];      a[j]=k;    }                    // /* Coloring */// l=0; c[a[0]]='A'; for(i=0;i<n;++i){    if(c[a[i]]=='Z'){       for(j=0;j<n;++j)         if(m[a[i]][j]==1){           if(c[j]!='Z'){             p[c[j]-'A']=1;            }        }      j=0;      for(k=0;k<4;k++){       if(p[k]==0&&j==0){         if(k==0)           c[a[i]]='A';         else if(k==1)           c[a[i]]='B';         else if(k==2)           c[a[i]]='C';         else           c[a[i]]='D';             j=1;           }            p[k]=0;          }       }   for(l=0;l<n;++l)      if(m[a[i]][l]==1){   if(c[l]=='Z'){     for(j=0;j<n;++j)        if(m[l][j]==1){          if(c[j]!='Z'){            p[c[j]-'A']=1;             }      }      j=0;      for(k=0;k<4;k++){        if(p[k]==0&&j==0){          if(k==0)            c[l]='A';          else if(k==1)            c[l]='B';          else if(k==2)            c[l]='C';          else            c[l]='D';          j=1;         }        p[k]=0;      }    }  }}                   // Bicoloring ? // l=0; for(i=0;i<n;++i)  if(c[i]=='C' || c[i]=='D')    { l=1; break; }if(l==0) printf("BICOLORABLE.\n");else printf("NOT BICOLORABLE.\n");} return 0;}`
asraful.ruet
New poster

Posts: 5
Joined: Wed Aug 11, 2010 8:52 am

Re: 10004 - Bicoloring WA

my problem gives me correct output for all possible input given in different threads, but it is WA. what is the problem can anyone tell me please...
here is the code
Code: Select all
`#include<iostream>#include<cstdio>#include<queue>#define MAX 201using namespace std;queue<int>que;int n,m;int path[MAX][MAX];int color[MAX];void initialize(){   int i,j;   for(i=0; i<MAX; i++){      for(j=0; j<MAX; j++){         path[i][j] = 0;      }      color[i] = 0;   }}int bfs(int u){   int temp;   int i;   que.push(u);   color[u] = 1;   while(!que.empty()){      temp = que.front();      que.pop();      for(i=0; i<n; i++){         if(path[temp][i]==1){            if(color[i]==0){               que.push(i);               if(color[temp] == 1)                  color[i] = 2;               else color[i] = 1;            }            else if(color[i] == color[temp])               return 0;         }      }   }   return 1;}int main(){   int a,b,i,value;   //freopen("10004.txt","r",stdin);   while(scanf("%d",&n)==1&&n){      scanf("%d",&m);      initialize();      for(i=0; i<m; i++){         scanf("%d %d",&a,&b);         path[a][b] = path[b][a] = 1;      }      if(m>0)         value = bfs(a);      else          value = 1;      if(value==0)printf("NOT BICOLORABLE.\n");      else printf("BICOLORABLE.\n");   }   return 0;}`
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
abid_iut
Learning poster

Posts: 80
Joined: Wed Jul 16, 2008 7:34 am

Re: 10004 - Bicoloring - Runtime Error

My solution is getting Runtime Error in 0.000s, but it works for all instances I've found in this board.
I don't know what is wrong. Is there a special test case that my code is not ready for?

Here is my code:
Code: Select all
`#include <cstdio>#include <cstdlib>#include <iostream>#include <vector>#include <cstring>using namespace std;#define MAX_V   205#define RED     0#define BLACK   1#define EMPTY  -1vector<int> colors(MAX_V, EMPTY);vector<int> grafo[MAX_V];   /* lista de adjacencias */void reset(){  for (int i = 0; i < MAX_V; i++)    {      colors[i] = EMPTY;      grafo[i].clear();    }}  int coloring(int v, int cor){  int anticor = 1-cor;  colors[v] = anticor;  vector<int>::iterator it;  for (it = grafo[v].begin(); it != grafo[v].end(); it++)    {      if (colors[*it] == EMPTY)   {     if (coloring(grafo[v][*it], anticor) == 0)       return 0;   }      else if (colors[*it] == anticor) return 0;    }  return 1;}int main(int argc, char** argv){  int   n_vertices, n_arestas;  /* number of vertices and arestas */  int   x, y;           int   is_bicolor;     while (1)    {      cin >> n_vertices;      if (n_vertices == 0) break;      cin >> n_arestas;      reset();            while (n_arestas--)         {     cin >> x >> y;     grafo[x].push_back(y);     grafo[y].push_back(x);   }            /* verifica se eh bicolor */      colors[0] = BLACK;      for (int i = 0; i < grafo[0].size(); i++)   if (colors[i] == EMPTY)     is_bicolor = coloring(i, BLACK);      if (is_bicolor)   cout << "BICOLORABLE." << endl;      else   cout << "NOT BICOLORABLE." << endl;    }  return 0;}`

victorhugo
New poster

Posts: 1
Joined: Tue Jul 26, 2011 1:08 am

Re: 10004 - Bicoloring

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 300int 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]`
roy780801
New poster

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

Re: 10004 - Bicoloring

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[i].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[u].size();i++)
{
int v=edges[u][i];
if(taken[v]==0)
{
if(taken[u]==1)
{
taken[v]=2;
Q.push(v);
}
else if(taken[u]==2)
{
taken[v]=1;
Q.push(v);
}

}
else if(taken[v]==taken[u])
{
//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[i]);
}
rashikh_08
New poster

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

PreviousNext

Who is online

Users browsing this forum: Bing [Bot] and 1 guest