hdu2444

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define  black 1
 4 #define  white -1
 5 int already[201];
 6 int in[201];
 7 int gr[201][201];
 8 int n;
 9 int v[201];
10 int pf,pe;
11 
12 int dfs(int a,int color){
13     v[a]=color;
14     int i;
15     int sign;
16     for(i=1;i<=n;++i){
17         if(i==a) continue;
18         if(gr[a][i]&&v[i]==0){
19             if((sign=dfs(i,-color))==-1) return -1;
20         }else if(gr[a][i]&&v[i]==color){
21             return -1;
22         }
23     }
24     return 1;
25 }
26 int judge(){
27     int i;
28     int sign;
29     memset(v,0,sizeof(v));
30     for(i=1;i<=n;++i){
31         if(0==v[i]){
32             if((sign=dfs(i,black))==-1) return -1;
33         }
34     }
35     return 1;
36 }
37 
38 int find(int a){
39     int i;
40     for(i=1;i<=n;++i){
41         if(v[i]==white&&gr[a][i]&&!in[i]){
42             in[i]=1;
43             if(already[i]==0||find(already[i])){
44                 already[i]=a;
45                 return 1;
46             }
47         }
48     }
49     return 0;
50 }
51 int main(){
52     int m;
53     int i,j;
54     int res;
55     while(~scanf("%d%d",&n,&m)){
56         res=0;
57         memset(gr,0,sizeof(gr));
58         while(m--){
59             scanf("%d%d",&i,&j);
60             gr[i][j]=1;
61             gr[j][i]=1;
62         }
63         if(judge()==-1){
64             printf("No
");
65             continue;
66         }
67 
68         memset(already,0,sizeof(already));
69         for(i=1;i<=n;++i){
70             memset(in,0,sizeof(in));
71             if(v[i]==black)
72                 if(find(i))
73                     res++;
74         }
75         printf("%d
",res);
76     }
77     return 0;
78 }