Page 4 of 7

Posted: Fri Aug 03, 2007 9:01 am
by Ron
please !! check the above program , and reply me any test cases , for what my program is wrong.............

Posted: Fri Aug 03, 2007 9:25 am
by rio
I can't understand your program well. Could you give a brief explanation of you algorithm ?
Then it well be much more easier to understand and debug.

EDIT : When you post your code, use Code tags.

EDIT : OK. I understood your algorithm. Actually its not correct. I'll make a critical test case.
----
Rio

Posted: Fri Aug 03, 2007 9:57 am
by rio
Try this case:

Code: Select all

4
3
0 3
1 2
2 3
0
Its obviously bicolorable.
----
Rio

Posted: Fri Aug 03, 2007 10:08 am
by Ron
Thank you very much .. :D Rio !!!

TLE

Posted: Sat Feb 02, 2008 11:14 pm
by Fuad Hassan EWU
HI i am having TLE in this prob, can u plz help?

AC

Re: 10004 - Bicoloring WA

Posted: Mon Sep 22, 2008 10:24 pm
by newton
Fuad Hassan EW

what was your algorithm?
you can place your code.

Re: 10004 - Bicoloring

Posted: Fri Dec 12, 2008 11:47 am
by 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...

Re: 10004 - Bicoloring

Posted: Thu Jun 18, 2009 10:44 am
by asqwzxdfercv
Below is my code. What is the problem :(

Code: Select all

spelling mistake. lol

Re: 10004 - Bicoloring

Posted: Fri Aug 28, 2009 10:32 pm
by Angeh
Can Sombody help me with my WA!!

Code: Select all

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

Re: 10004 - Bicoloring

Posted: Mon Sep 28, 2009 7:58 am
by 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;
}

Re: 10004 - Bicoloring

Posted: Wed Oct 14, 2009 8:10 pm
by 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)

Re: 10004 - Bicoloring

Posted: Sat Aug 14, 2010 8:57 pm
by 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."

Re: 10004 - Bicoloring

Posted: Sun Sep 12, 2010 6:11 am
by 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;
}


Re: 10004 - Bicoloring WA

Posted: Fri Apr 08, 2011 12:26 pm
by 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;
}


Re: 10004 - Bicoloring - Runtime Error

Posted: Tue Jul 26, 2011 2:13 am
by 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.