Bicoloring

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=945 

Online Judge

성공여부 : 실패(Wrong Answer)

아이디어 : 큐를 사용한 넓이 탐색

실패이유 예상 : 큐의 사이즈를 넘어가는 상황이 발생? 또는 넓이 탐색으로 해결이 안될수도?

수정 : 

(10:21) - 성공(Accept)

출력구문에서 마지막 BICOLORABLE. 의 .을 추가하니 Accept

 

#include <stdio.h>

int map[200][200];
int color[200];
int queue[40000];
int top, bot;

int main()
{
    int n, l, i, j, x, y, root;

    while (scanf("%d", &n), n != 0)
    {

        for (i = 0; i < n; i++)
        { // -1 not input, 1 on, 0 off//init
            color[i] = -1;
            for (j = 0; j < n; j++)
                map[i][j] = 0;
        }

        scanf("%d", &l);
        for (i = 0; i < l; i++)
        {
            scanf("%d %d", &x, &y);
            map[x][y] = 1;
            map[y][x] = 1;
        }

        color[0] = 1;   // first point is on
        top = 0;        // queue's top
        bot = 0;        // queue's tail
        root = 1;       // roop on
        queue[top] = 0; // first point is 0

        while (bot <= top && root)
        { // width search
            x = queue[bot++];
            for (i = 0; i < n; i++)
                if (map[x][i] == 1)
                    if (color[i] == -1)
                    {
                        queue[++top] = i;
                        color[i] = !color[x];
                    }
                    else if (color[x] == color[i])
                    {
                        root = 0;
                        break; // find NOT BICOLORABLE
                    }
        }

        if (root)
            printf("BICOLORABLE.\n");
        else
            printf("NOT BICOLORABLE.\n");
    }
    return 0;
}

 

> uva 사이트에서 채점시 주석은 지우셔야 컴파일에러가 안나는 거 같습니다.