二分图又叫二部图，是图论中的一种特殊模型。
假设S=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，就可以称图S为一个二分图。简单来说，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
二分图的匹配
给定一个二分图S，在S的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
最大匹配是所有极大匹配当中边数最大的一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
完全匹配一定是极大匹配，但是极大匹配不一定是完全匹配。下图就是一个最大匹配。
二分图的判断
对于二分图的判断方法最常见的是染色法，就是对每一个点进行染色操作，只用黑白两种颜色，能不能使所有的点都染上了色且相邻两个点的颜色不同？如果可以那么这个图就是一个二分图，对于判断是否是一个二分图的方法可以用dfs和bfs两种方式去实现。
二分图的最大匹配
给定一个二分图S，在S的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
首先要了解两个概念：
|交替路|从一个未匹配的点出发，依次经过未匹配边、匹配边、未匹配边….
|增广路|从一个未匹配的点出发，走交替路，到达了一个未匹配过的点。
对于求二分图最大匹配的算法可以用网络流去跑一个最大流求解，还可以用二分图的常见算法匈牙利算法，这个算法的核心就是去找未匹配的点，然后从这个点出发去寻找增广路，因为增广路有几个主要的特点：
增广路有奇数条边 。
路径上的点一定是一个在X边，一个在Y边，交错出现。
起点和终点都是目前还没有配对的点。
未匹配边的数量比匹配边的数量多1。
重点是第4点，我们可以根据此特性，把这条增广路中的匹配边改为未匹配边，把未匹配边改为匹配边，这样我们就可以使总匹配边数+1了，根据上面的图得出下图，很显然匹配边多了一条。
vector<int>G[maxn];//存边
int col[maxn];//标记顶点颜色
int n,m;//点和边的个数
bool bfs(){ //BFS判断二分图
queue<int>q;
q.push(1);//放入第一个点
memset(col,0,sizeof(col));
col[1]=1;//先标记第一个点为1
while(!q.empty())
{
int v=q.front();
q.pop();
for(int i=0; i<G[v].size(); i++)
{
int xx=G[v][i];
if(col[xx]==0){//判断这个点是否标记过
col[xx]=-col[v];//没有标记过就标记上与v相反的颜色
q.push(xx);
}
else
{
if(col[v]==col[xx]){//如果颜色冲突说明不是二分图
return false;
}
}
}
}
return true;
}vector<int> G[maxn];//存边
int pre[maxn];//记录匹配点
bool vis[maxn];//标记是否匹配过
int n,m;//n个点 m条边
bool dfs(int x)
{ //匈牙利算法：二分图的最大匹配
for(int i=0; i<G[x].size(); i++)
{
int v=G[x][i];
if(vis[v]==false){//判断是否标记过
vis[v]=true;
if(pre[v]==-1||dfs(pre[v])){// 判断当前点是否匹配过 dfs为判断这个点能不能和其他的点匹配
pre[v]=x;
return true;
}
}
}
return false;
}
int Fun()
{
int sum=0;
memset(pre,-1,sizeof(pre));
for(int i=1; i<=n; i++)
{
memset(vis,false,sizeof(vis));//每次遍历都需要初始化
if(dfs(i)){
sum++;
}
}
return sum;
}