Problem 10004 Bicoloring，著色問題

此題為一老老實實的 m - 著色問題，這用回溯演算法就可以解決了。

首先將節點能連接的通通將值改為 1，因為是雙向的，所以也要將反向連接的也改為 1，C 語言程式碼如下：

int pathNum, f, t;
scanf("%d", &pathNum);
for (i = 0; i < pathNum; i ++)
    scanf("%d %d", &f, &t), W[f + 1][t + 1] = W[t + 1][f + 1] = 1;

利用回溯演算法找出有幾種塗色方式，C 語言程式碼如下：

int promising(int i)
{
    int j;
    for (j = 1; j < i; j ++)
    {
        if (W[i][j] && vcolor[i] == vcolor[j])
            return 0;
    }
    return 1;
}

void m_coloring(int i)
{
    int color, j;
    if (i == n + 1)
        total ++;
    else
    {
        for (color = 1; color <= m; color ++)
        {
            vcolor[i] = color;
            if (promising(i)) m_coloring(i + 1);
        }
    }
}

最後只須在主程式內如此呼叫以及印出：

total = 0;
m_coloring(1);
if (total == 0) printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");

By David.K

p10004題目連結
回ACM題庫目錄
回首頁