UVA_10004
对于这个题目,我们可以直接模拟染色的过程即可,如果发现要涂某一块时这个块已经被涂了色,并且与我们要使用的颜色不同的话,就说明这个图不能被染成BICOLORABLE的。
#include<stdio.h>
#include<string.h>
int G[210][210],q[210],paint[210],n;
int dfs(int u,int color)
{
int v;
for(v=0;v<n;v++)
if(G[u][v])
{
if(paint[v]!=-1&&paint[v]!=color)
return 0;
else if(paint[v]==-1)
{
paint[v]=color;
if(!dfs(v,1-color))
return 0;
}
}
return 1;
}
int main()
{
int i,j,k,m,u,v,front,rear;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
scanf("%d",&m);
memset(G,0,sizeof(G));
for(i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
G[u][v]=G[v][u]=1;
}
memset(paint,-1,sizeof(paint));
paint[0]=0;
if(dfs(0,1))
printf("BICOLORABLE.\n");
else
printf("NOT BICOLORABLE.\n");
}
return 0;
}