首页 > 代码库 > uva 10004(图)
uva 10004(图)
题解:本来想着用dfs,后来写着写着就成普通的循环了,将起始点0先涂色,然后把和他相邻的其他点涂成另一种颜色,再从下一个点搜索,如果有连线但已经被涂色且和自己颜色一样就可以判断结果是错。
#include <stdio.h> #include <string.h> const int N = 200 + 5; int n, l, G[N][N], vis[N], flag; void init() { memset(G, 0, sizeof(G)); memset(vis, 0, sizeof(vis)); flag = 0; } void dfs(int x) { for (int i = 0; i < n; i++) { if (G[x][i] && vis[i] == 0) { if (vis[x] == 1) vis[i] = 2; else vis[i] = 1; } else if (G[x][i] && vis[i] != 0) { if (vis[i] == vis[x]) { flag = 1; } } } } int main () { int v1, v2; while (scanf("%d", &n) && n) { init(); scanf("%d", &l); for (int i = 0; i < l; i++) { scanf("%d %d", &v1, &v2); G[v1][v2] = G[v2][v1] = 1; } vis[0] = 1; for (int i = 0; i < n; i++) dfs(i); if (flag) printf("NOT BICOLORABLE.\n"); else printf("BICOLORABLE.\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。