uva 10004 Bicoloring(二染色)

这道题我始终还是看了题解，不过有进步的是我看了他的想法自己实现的，恩恩，就是要这样，，一定得先有个正确的

想法，这样才能做对题，敲代码之前想法就错了那么一定做不对题目的，我之前想的是只要存在环就不会实现去全部染

色，其实是可以的，当这个环是奇数的时候就可以，偶数的时候不可以。所以我用的dfs每次遍历的时候遇到没有染色

的就染色，遇到染过色的就判断一下是否是一样的颜色。

贴代码：

#include<stdio.h>#include<stdlib.h>#include<string.h>int visit[205];int map[205][205];int m,n,flag;void dfs(int x){for(int i=0; i<n; i++){if(map[x][i]==1){if(visit[i]!=0){if(visit[i]==visit[x]){flag = 0;return;}}else{if(visit[x]==2)visit[i] = 3;elsevisit[i] = 2;dfs(i);}}}return ;}int main(){int i,x,y;while(scanf("%d",&n),n!=0){memset(visit,0,sizeof(visit));memset(map,0,sizeof(map));scanf("%d",&m);for(i=0; i<m; i++){scanf("%d%d",&x,&y);map[x][y]=map[y][x]=1;}for(i=0; i<n; i++){flag = 1;if(visit[i]==0){visit[i] = 2;dfs(i);}if(flag == 0){break;}}if(flag)puts("BICOLORABLE.");elseputs("NOT BICOLORABLE."); }return 0;}

好好扮演自己的角色，做自己该做的事

相关文章：

你感兴趣的文章：

标签云：