一開始想說沒這麼難吧?不就填色嗎!
填完答案就出來了!
不過像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); } } }
沒有留言:
張貼留言