2010年02月07日星期日.sgu172 判斷一個(gè)圖是否是二分圖 黑白染色
題意解釋：給出一個(gè)圖的邊，對這個(gè)圖進(jìn)行黑白染色，不能染色則輸出no
能染色輸出黑色或者白色的個(gè)數(shù)，并且輸出點(diǎn)的序號
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