題目鏈接

題意： n個(gè)學(xué)生，m對關(guān)系，每一對互相認(rèn)識的能住一個(gè)房間。問否把這些學(xué)生分成兩組，要求每組的學(xué)生都互不認(rèn)識。求最多須要多少個(gè)房間。

能否分成兩組？也就是說推斷是不是二分圖，推斷二分圖的辦法，用 染色法

把初始點(diǎn)染成黑色，然后與之相連的染成白色，反復(fù)，使路徑黑白相間，

假設(shè)當(dāng)前點(diǎn)的顏色和與他相連點(diǎn)的顏色同樣時(shí)，則說明這個(gè)圖不是二分圖

求最多須要多少個(gè)房間？也就是求最大匹配數(shù)。

      #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 310;
const int maxm = 100001;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
const int N = 50010;
int ma[maxn][maxn];
int line[maxn],color[maxn];
bool vis[maxn];
int k,n,m;
bool flag;
int DFS(int u)
{
    for(int  v = 1;v<=n;v++)
    {
        if(ma[u][v]==1 && !vis[v])
        {
            vis[v] = 1;
            if(line[v]==-1 || DFS(line[v]))
            {
                line[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
void dfs(int u,int st)
{
    if(flag == false)
        return ;
    for(int v = 1;v <= n;v++)
    {
        if(ma[u][v])
    {
        if(!color[v])
        {
            color[v]= -st;//黑染白 / 白染黑
            dfs(v,color[v]);
        }
        else if(color[v]==st)
        {
            flag = false;
            return;
        }

    }
    }

}
bool judge()
{
    flag = true;
    color[1] = 1 ;//1代表黑色，-1代表白色
    dfs(1,1) ;
    return flag;
}
int K_M()
{
    int ans = 0;
    memset(line,-1,sizeof(line));
    for(int i  = 1;i<=n;i++)
    {
        init(vis);
        ans += DFS(i);
    }
    return ans;
}
int main()
{
    int a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(ma);
        memset(color,0,sizeof(color));
        for(int i = 1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            ma[a][b]  = 1;
        }
        if(!judge())
        {
            puts("No");
            continue;
        }
        int ans = K_M();
        printf("%d\n",ans);
    }
    return 0;
}