ACM 10004 Bicoloring

第一次寫graph，好刺激……

一開始想說沒這麼難吧？不就填色嗎！
填完答案就出來了！
不過像input為
1 2
3 4
2 3
就會gg了。
所以一定要是traversal + 填色兩個動作。
光是填或是光是traversal是不行的。

填色 + DFS檢查填色狀況。
利用adjacency list建graph。
之後從graph[0]開始填色（填在每個graph[i]），
填完每個跟graph[0]相連的node之後，做DFS走訪graph，
一樣先做填色的動作，再做DFS。
若填色時發現該node顏色與要填的顏色不一，
表示沒有bicolor的形式。
若能順利填完色走訪完整個graph，表示有bicolor的形式。

總覺得寫得很髒 orz，不知道有沒有其他比較好的方式，
填色O(e)感覺花了不少時間。

這個問題其實是一個Bipartite Graph。
解了Bipartite Graph這題就能解了，這題能解了Bipartite Graph也可以解了。

/* ACM 10004 Bicoloring
 * mythnc
 * 2011/12/26 19:44:34   
 * run time: 0.012
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXNODE 199
#define TRUE    1
#define FALSE   0

enum color {none, white, black};

typedef struct node {
    int n;
    enum color c;
    struct node *next;
} Node;

void init(Node **);
void input(Node **, int, int);
int check(Node **, int);
void freeg(Node **, int);

int visited[MAXNODE];

int main(void)
{
    int n, e, u, v, i;
    Node *graph[MAXNODE];

    while (scanf("%d", &n) && n != 0) {
        scanf("%d", &e);
        init(graph);
        for (i = 0; i < e; i++) {
            scanf("%d %d", &v, &u);
            input(graph, u, v);
            input(graph, v, u);
        }
        if (check(graph, 0))
            printf("BICOLORABLE.\n");
        else
            printf("NOT BICOLORABLE.\n");
        freeg(graph, n);
    }

    return 0;
}

/* init: initialize graph node to NULL and visited to zero */
void init(Node **graph)
{
    int i;

    for (i = 0; i < MAXNODE; i++) {
        graph[i] = NULL;
        visited[i] = FALSE;
    }
}

/* input: receive input data */
void input(Node **graph, int u, int v)
{
    Node *tmp, *pt;

    tmp = (Node *)malloc(sizeof(Node));
    tmp->n = u;
    tmp->c = none;
    tmp->next = NULL;
    if (!graph[v]) {
        graph[v] = (Node *)malloc(sizeof(Node));
        graph[v]->n = v;
        graph[v]->c = none;
        graph[v]->next = tmp;
    }
    else {
        pt = graph[v];
        while (pt->next)
            pt = pt->next;
        pt->next = tmp;
    }
}

/* check(dfs): check each node and
 * its adjacency are different colors.
 * if have same color stop dfs and return FALSE
 * else do dfs to the end and return TRUE */
int check(Node **graph, int n)
{
    enum color c;
    Node *pt;

    pt = graph[n];
    visited[n] = TRUE;
    if (pt->c == none) {
        pt->c = white;
        c = black;
    }
    else if (pt->c == white)
        c = black;
    else
        c = white;
    for (pt = pt->next; pt; pt = pt->next)
        if (graph[pt->n]->c == none)
            graph[pt->n]->c = c;
        else if (graph[pt->n]->c == c)
            ;
        else
            return FALSE;
    for (pt = graph[n]->next; pt; pt = pt->next)
        if (!visited[pt->n])
            if (!check(graph, pt->n))
                return FALSE;

    return TRUE;
}

/* freeg: free link node */
void freeg(Node **graph, int n)
{
    int i;
    Node *pt, *tmp;

    for (i = 0; i < n; i++) {
        pt = graph[i];
        while (pt) {
            tmp = pt;
            pt = pt->next;
            free(tmp);
        }
    }
}