UVA 10004   Bicoloring 

題意：輸入資料，構造出一個圖，你能用2種顔色去填充該圖的每個節點，如果有2個相鄰結點顔色相同，該圖為NOT Bicoloring，如果每相鄰顔色都不同，則為Bicolring。 思路：搜尋的 水題，用DFS從每個點為起點都找一次，當找到回路的時候，判斷該回路結點個數如果是奇數，必然有2個相鄰結點顔色會相同，跳出。如果是偶數，那就。。。繼續找吧 代碼：

#include <stdio.h>
#include <string.h>

int n, m;
int lu[205][205];
int num[205];
int visd[205];
int vis[205][205];
int a, b;
int judge;
void dfs(int n, int nu)
{
    for (int i = 0; i < num[n]; i ++)
    {
	if (vis[n][lu[n][i]] == 0)
	{
	    if (visd[lu[n][i]] == 1)
	    {
		if (nu % 2)
		{
		    judge = 1;
		    return;
		}
		return;
	    }
	    visd[lu[n][i]] = 1;
	    vis[n][lu[n][i]] = vis[lu[n][i]][n] = 1;
	    dfs(lu[n][i], nu + 1);
	    visd[lu[n][i]] = 0;
	    vis[n][lu[n][i]] = vis[lu[n][i]][n] = 0;
	}
    }
}
int main()
{
    while (scanf("%d", &n) != EOF && n)
    {
	judge = 0;
	memset(lu, 0, sizeof(lu));
	memset(num, 0, sizeof(num));
	scanf("%d", &m);
	for (int i = 0; i < m; i ++)
	{
	    scanf("%d%d", &a, &b);
	    lu[a][num[a]]  = b;
	    lu[b][num[b]] = a;
	    num[a] ++;
	    num[b] ++;
	}
	for (int i = 0; i < n; i ++)
	{
	    memset(visd, 0, sizeof(visd));
	    memset(vis, 0, sizeof(vis));
	    visd[i] = 1;
	    dfs (i, 1);
	    if (judge)
	    {
		printf("NOT BICOLORABLE.\n");
		break;
	    }
	}
	if (!judge)
	    printf("BICOLORABLE.\n");
    }
    return 0;
}