uva 10004(图)

题解：本来想着用dfs，后来写着写着就成普通的循环了，将起始点0先涂色，然后把和他相邻的其他点涂成另一种颜色，再从下一个点搜索，如果有连线但已经被涂色且和自己颜色一样就可以判断结果是错。

#include 
#include 
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;elsevis[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");elseprintf("BICOLORABLE.\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！