The Accomodation of Students

4 41 21 31 42 36 51 21 31 42 53 6 Sample Output
No3 
题目大意:
                      给你一张图，判断是否能构成二分图，如果能求出最大匹配
题目思路：
                可以直接bfs进行染色，如果在同一集合中的点的颜色不相同则说名不能构成，否则能够成二分图然后进行最大匹配
AC代码：
#include<cstring>#include<cstdio>#include<vector>#include<queue>const int maxn = 250;using std::vector;using std::queue;vector<int>edge[maxn];bool vis[maxn];int link[maxn];int n,m;bool dfs(int u){    for(int i=0;i<edge[u].size();i++){        int v = edge[u][i];        if(!vis[v]){            vis[v]=true;            if(link[v]==-1||dfs(link[v])){                link[v]=u;                return true;            }        }    }    return false;}bool bfs(int u){           //bfs染色判断    link[u]=0;    queue<int>q;    q.push(u);    while(!q.empty()){        u = q.front();q.pop();        for(int i=0;i<edge[u].size();i++){            int v = edge[u][i];            if(link[v]==-1){link[v]=link[u]^1;q.push(v);}            else {                if(link[v]==link[u])return false;   //在不同集合中且颜色相同            }        }    }    return true;}int main(){    while(~scanf("%d%d",&n,&m)){        memset(link,-1,sizeof(link));        memset(edge,0,sizeof(edge));        while(m--){            int u,v;scanf("%d%d",&u,&v);            edge[u].push_back(v);            edge[v].push_back(u);        }        int flag=0;        for(int i=1;i<=n;i++){            if(link[i]==-1){                if(!bfs(i)){                    flag=1;                    break;                }            }        }        if(flag){            printf("No/n");            continue;        }        memset(link,-1,sizeof(link));        int ans = 0;        for(int i=1;i<=n;i++){            memset(vis,false,sizeof(vis));            if(dfs(i))ans++;        }        printf("%d/n",ans/2);    }    return 0;}