题目链接：https://vjudge.net/problem/18341/origin
题目大意：给你n个学生，m个朋友关系。问你能不能把学生分成二组，每一组的人没有互相认识。如果可以，这样对认识的人分配双人房。问你最多可以分配双人房。

思路：判断是不是二分图，如果是最大匹配/2就可以了。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int g[205][205]={0};//存图
int vist[205]={0};//染每种颜色的节点
int n;


int isTwo()//判断是否为二分图
{
    queue<int>q;
    memset(vist,0,sizeof(vist));
    q.push(1); vist[1]=1;
    while(!q.empty())
    {
        int p=q.front(); q.pop();
        for(int j=1;j<=n;j++)
        if(g[p][j])
        {
            if(vist[j]==0)
            {
                if(vist[p]==1)vist[j]=2;else vist[j]=1;
                q.push(j);
            }
            else if(vist[j]==vist[p])
                return 0;
        }
    }
    return 1;
}

const int N=205;  // 最大点数
const int INF=1<<28;  // 距离初始值

int Mx[N];  //Mx[i]表示左集合i顶点所匹配的右集合的顶点序号
int My[N];  //My[i]表示右集合i顶点所匹配的左集合的顶点序号
int dx[N];
int dy[N];
bool used[N];

int Nx,Ny,dis;


 //寻找 增广路径集
bool searchP()
{
    dis=INF;
    int i,v,u;
    std::queue<int> Q;

    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(i=1;i<=Nx;i++)
    {   //cx[i]表示左集合i顶点所匹配的右集合的顶点序号
        if(Mx[i]==-1)
        {
            //将未遍历的节点 入队 并初始化次节点距离为0
            Q.push(i);
            dx[i]=0;
        }
    }
    //广度搜索增广路径
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        if(dx[u]>dis) break;
        //取右侧节点
        for(v=1;v<=Ny;v++)
        {
            //右侧节点的增广路径的距离
            if(g[u][v]&&dy[v]==-1)
            {
                dy[v]=dx[u]+1;   //v对应的距离 为u对应距离加1
                if(My[v]==-1) dis=dy[v]; //如果该点未被匹配，那么增广路形成
                else                       //如果该点匹配了，那么接着往下搜
                {
                    dx[My[v]]=dy[v]+1;
                    Q.push(My[v]);
                }
            }
        }
    }
    return dis!=INF;
}

//寻找路径 深度搜索
bool DFS(int u)
{
    int v;
    for(v=1;v<=Ny;v++)
    {
        //如果该点没有被遍历过 并且距离为上一节点+1
        if(g[u][v]&&!used[v]&&dy[v]==dx[u]+1)
        {
            //对该点染色
            used[v]=true;
            if(My[v]!=-1&&dy[v]==dis) continue; //如果该点已经被匹配了并且为最后一个匹配点，那么这条路径不是增广路。即是说这条路的结点已经匹配
            if(My[v]==-1||DFS(My[v]))  //如果该点未匹配或者后面的点能腾出位置，那么这就是增广路
            {
                My[v]=u;
                Mx[u]=v;
                return true;
            }
        }
    }
    return false;
}

//得到最大匹配的数目
int Hungary()
{
    int u;
    int ret=0;
    memset(Mx,-1,sizeof(Mx));
    memset(My,-1,sizeof(My));
    while(searchP())  //如果存在增广路
    {
        memset(used,false,sizeof(used));
        for(u=1;u<=Nx;u++)
           if(Mx[u]==-1&&DFS(u))  ret++;
    }
    return ret;
}

int main()
{
    int k;
	while(~scanf("%d%d",&n,&k))
    {
        memset(g, 0, sizeof(g));
        for(int i=0;i<k;i++)
        {
            int u, v;
            scanf("%d%d",&u,&v);
            g[u][v]=1;
            g[v][u]=1;
        }
        Ny=Nx=n;

        if(isTwo())
        {
            int ans=Hungary();
            printf("%d\n",ans/2);
        }
        else
        {
            printf("No\n");
        }
    }

	return 0;
}