Why so serious? --[NKU]schindlerlee

2010年02月07日星期日.sgu172 判断一个图是否是二分图 黑白染色

2010年02月07日星期日.sgu172 判断一个图是否是二分图 黑白染色
题意解释:给出一个图的边,对这个图进行黑白染色,不能染色则输出no
能染色输出黑色或者白色的个数,并且输出点的序号
 1 
 2 const int N = 256;
 3 int g[N][N],n,m,vis[N];
 4 const int black = 1;
 5 const int white = 2;
 6 int res ;
 7 
 8 bool dfs(int u,int color)
 9 {
10   vis[u] = color;
11   if (color == black) { res++; }
12   if (color == black) { color = white; }
13   else { color = black; }
14 
15   int i;
16   for (i = 1;i <= n;i++) {
17       if (g[u][i]) {
18           if (vis[i] == 0) {
19               if(!dfs(i,color)) return false;
20           }else if (vis[i] != 0 && vis[i] != color) {
21               return false;
22           }
23       }
24   }
25   return true;
26 }
27 
28 bool dyeing()
29      //染色
30 {
31   for (int i = 1;i <= n;i++) {
32       if (vis[i] == 0) {
33           if(!dfs(i,black)) {
34               return false;
35           }
36       }
37   }
38   return true;
39 }
40 
41 int main()
42 {
43   int i,j,k,a,b;
44   scanf("%d %d",&n,&m);
45   for (i = 0;i < m;i++) {
46       scanf("%d%d",&a,&b);
47       g[a][b] = g[b][a] = 1;
48   }
49   if (!dyeing()) {
50       printf("no\n");
51   }else {
52       printf("yes\n");
53       printf("%d\n",res);
54       for (i = 1;i <= n;i++) {
55           if (vis[i] == black) {
56               printf("%d ",i);
57           }
58       }
59       printf("\n");
60   }
61   return 0;
62 }
63 


posted on 2010-02-07 20:00 schindlerlee 阅读(1506) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理