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