10004 - Bicoloring

[rio]

Try this case:

Code: Select all

4
3
0 3
1 2
2 3
0


Its obviously bicolorable.
----
Rio

[Ron]

Thank you very much .. Rio !!!

[Fuad Hassan EWU]

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

AC

[newton]

Fuad Hassan EW

what was your algorithm?
you can place your code.

[empo]

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...

[asqwzxdfercv]

Below is my code. What is the problem

Code: Select all

spelling mistake. lol


[Angeh]

Can Sombody help me with my WA!!

Code: Select all

 GoT AC --
Dont Forget The dot at the end of your Lines

[asif_khan_ak_07]

I am getting WA in this problem....please help

Code: Select all

#include<stdio.h>
#include<queue>
#define  MAX 201
using 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;
}

[arifcsecu]

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

"




your program reads input from a file
how can it possible
just comment the line like
// freopen("1004.txt","r",stdin)

[valkov]

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."

[asraful.ruet]

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

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;
}



[abid_iut]

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 201
using 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;
}



[victorhugo]

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  -1

vector<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;
}


Thanks in advance.

[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]

[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[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]);
}