二分图

1.是什么

一种特殊的图，这种图可以把图中的点分成两个集合，所有的边都在这两个集合之间，也就是说集合内部的点之间是没有边的。

2.怎么判断

一般来说用染色法判断，从任意一个结点开始交替染色，若与某节点连边的结点已被染色，且颜色与该节点相同，则该图不是二分图。

代码：

int paint(int x,int idx){
    color[x]=idx;
    for(int i=head[x];i;i=nxt[i]){
        if(!color[ve[i]]){
            if(!paint(ve[i],3-idx)) return 0;
        }
        else if(color[x]==color[ve[i]]) return 0;
    }
    return 1;
}

3.二分图的匹配

如图1这样一个二分图

图2即为它的极大匹配

图三即为它的最大匹配，同时也是完全匹配

 来自博客：https://blog.csdn.net/weixin_46522531/article/details/128469751 写的真的很好

最后一句话可改为 完全匹配一定是最大匹配，但最大匹配不一定是完全匹配

4.如何求最大匹配

 增广路：连接两个未匹配顶点，且该路径的组成成分（？）为未匹配、匹配交替，且最后由未匹配结束

如果我们在二分图其中一个点的集合里一直找增广路直到找不到为止，此时就可以得到最大匹配了，匈牙利算法

果然这里还是讲不清楚 请移步这篇博客：https://zhuanlan.zhihu.com/p/402091571 看看动图，多读几遍就懂了

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long N=1e6+10;
int n,m,e,u,v,ver[N],cnt=0;
int book[550][550],h[N];
int dfs(int x){
    for(int i=1;i<=m;i++){
        if(book[x][i]==1&&ver[i]==0){
            ver[i]=1;
            if(h[i]==0||dfs(h[i])){
                h[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;i++){
        scanf("%d%d",&u,&v);
        book[u][v]=1;
    }
    for(int i=1;i<=n;i++){
        memset(ver,0,sizeof(ver));
        cnt+=dfs(i);
    }
    printf("%d\n",cnt);
    return 0;
}

如果还是不太明白移步下面几篇博客：

https://zhuanlan.zhihu.com/p/353364452

https://blog.csdn.net/weixin_46522531/article/details/128469751

https://zhuanlan.zhihu.com/p/402091571

https://blog.csdn.net/dark_scope/article/details/8880547