模擬染色，因為只有兩種顏色，所以分別用 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;
}
?
)
