ACM 10004 - Bicoloring

#include <stdio.h>
#include <stdlib.h>
#define SIZE 201

int n, m = 2;
int W[SIZE][SIZE], vcolor[SIZE];
int total = 0; 
                       
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);
        }
    }
}

int main()
{
    int i, j;
    while (scanf("%d", &n) == 1 && n)
    {
        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;
        total = 0;
        m_coloring(1);
        if (total == 0) printf("NOT BICOLORABLE.\n");
        else printf("BICOLORABLE.\n");
        for (i = 1; i <= n; i ++)
        {
            vcolor[i] = 0;
            for (j = 0; j < n; j ++)
                W[i][j] = 0;
        }
    }
    return 0;
}

回目錄
回首頁