UVA 10004 - Bicoloring

模拟染色，因为只有两种颜色，所以分别用 0、 1 代表这两种颜色，然后从0开始深搜，如果

每个点都能染上色，且相邻两点的颜色不同，则符合要求。

#include<stdio.h>
#include<string.h>
#define MAXN 210

int map[MAXN][MAXN];
int paint[MAXN];
int u, v, M, N;

bool dfs( int i, int color)
{
for( int j = 0; j < N; j ++)
{
if( map[i][j])
{
if( paint[j] != -1 && paint[j] != color)
return false;
else if( paint[j] == - 1)
{
paint[j] = color;
if( !dfs( j, 1 - color)) //用 0和1分别代表白‘黑两种颜色
return false;
}
}
}
return true;
}

void init()
{
scanf( "%d", &M);
memset( map, 0, sizeof map);
for( int i = 0; i < M; i ++)
{
scanf( "%d%d", &u, &v);
map[u][v] = map[v][u] = true;
}
memset( paint, -1, sizeof paint);
paint[0] = 1;// 如果这里等于0的话则dfs( 0, 1)。
}

int main()
{
while( scanf( "%d", &N), N)
{
init();
if( dfs( 0, 0))
printf( "BICOLORABLE.\n");
else
printf( "NOT BICOLORABLE.\n");
}
return 0;
}

 

转载于:https://www.cnblogs.com/Yu2012/archive/2011/12/06/2278372.html

总结

以上是生活随笔为你收集整理的UVA 10004 - Bicoloring的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。