HDU 2444：用BFS染色判断是否为二分图最后为什么要除2，因为匹配的时候实际上是双向结果，就是a->b和b->a分别是俩条线
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n,m;
int vis[201];
int match[201];
//int Map[201][201];
//queue<int>q[205];
vector<int> q[205];
int check(){
queue<int> c;
memset(vis, 0, sizeof vis);
c.push(1);
vis[1] = 1;
while(!c.empty()){
int u = c.front();
c.pop();
//while(!q[u].empty())
for(int i=0; i<q[u].size(); i++)
{
//int v = q[u].front();
//q[u].pop();
int v=q[u][i];
if(!vis[v]){
vis[v] = vis[u] == 1? 2:1;
c.push(v);
}
else
{
if(vis[u]==vis[v]) return 0;
}
}
}
return 1;
}
int Find(int x){
/* 这种方法内存会Memory Limit Exceeded
for(int i=1; i<=n; i++){
if(vis[i] == 0 && Map[x][i]){
vis[i] == 1;
if(match[i] == -1 || Find(match[i])){
match[i] = x;
return 1;
}
}
}
*/
for(int i=0; i<q[x].size(); i++){
int v = q[x][i];
if(vis[v] == 0){
vis[v] = 1;
if(match[v] == -1 || Find(match[v])){
match[v] = x;
return 1;
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d", &n, &m)){
/*清除残留*/
for(int i=0; i<205; i++)
q[i].clear();
memset(Map, 0, sizeof Map);
int a,b;
for(int i=0; i<m; i++){
scanf("%d%d", &a, &b);
//q[a].push(b);
q[a].push_back(b);
//q[b].push(a);
q[b].push_back(a);
//Map[a][b] = 1;
//printf("-------------\n");
}
if(check() == 0) {
printf("No\n");
//break;
}
else{
memset(match, -1, sizeof match);
int ans = 0;
for(int i=1; i<=n; i++){
memset(vis, 0, sizeof vis);
if(Find(i)) ans++;
}
printf("%d\n", ans/2);
}
}
return 0;
}
