uva 10004 Bicoloring

用 adjacent list 把圖存好後，走一次圖，可以採用 BFS，先把第一個 node 塗上顏色，用此點

開始走，鄰居塗上和自己不同的顏色，如果發現鄰居已經有顏色了，判斷是否相同顏色，相

同 => notbicolorable，不相同 => OK


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

int maps[201][201];

int BFS(){
    int i,ok;
    int queueList[201]={0},top,head,extract,neighbor;
    int color[201]={0}; /* color : 1, 2 */

    ok=1;

    head=top=0;
    queueList[top]=1; color[1]=1;
    while(head<=top){
        extract=queueList[head++];

        for(i=1;i<=maps[extract][0];i++){
            neighbor=maps[extract][i];

            if(color[neighbor]==0){
                color[neighbor]= (color[extract]==1) ? 2 : 1;
                queueList[++top]=neighbor;
            }else if(color[neighbor] == color[extract]){
                ok=0;
                head=top+1; /* break while */
                break;
            }
        }
    }

    return ok;
}

int main(void){
    int nodes,edges;
    int i,src,dest,outcome;


    while(scanf("%d",&nodes)!=EOF){
        if(!nodes) break;

        scanf("%d",&edges);

        memset(maps,0,sizeof(maps));
        for(i=0;i<edges;i++){
            scanf("%d %d",&src,&dest);
            maps[src+1][++maps[src+1][0]]=dest+1;
            maps[dest+1][++maps[dest+1][0]]=src+1;
        }

        outcome=BFS();

        if(outcome==1)
            printf("BICOLORABLE.\n");
        else
            printf("NOT BICOLORABLE.\n");
    }

    return 0;
}