概念：
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
是不是有些抽象？
整点直观的：
如果一个图能转化成上面的这种亚子，那它就是一个二分图了。
那么，第一个问题就来了：
怎么判断一个图是不是二分图？
答案是：染色法。
观察一下：
二分图中父子节点所在的集合是不一样的，
不一样的集合便将点染成不同的颜色。
代码解释：
bool check(int mid){
queue<int>q;
memset(color,0,sizeof(color));//每一次check前要清零
for(int i=1;i<=n;i++){
if(color[i]) continue;//已经染过色的话就直接进行判断了
q.push(i);color[i]=1;//用bfs防止爆栈
while(!q.empty()){
int x=q.front();q.pop();
for(int j=head[x];j;j=eg[j].nex){
int y=eg[j].to;
if(!color[y]){
color[y]=3-color[x];//染成不同的颜色——1，2
q.push(y);
}
else if(color[y]==color[x]){//同色，矛盾，不是二分图
return false;
}
}
}
}
return true;
}
OK，接下来就是解决最大匹配的问题了。
这里有一篇文章讲的很不错，推荐一下：https://blog.csdn.net/JarjingX/article/details/8181073
大概思路是这样的：
把两个集合当做需要结婚的男人和女人，
给出他们的喜欢关系，
问最多能组成几对配偶。
如果这个男生喜欢的女生还没有结婚，
那就先让他们两个在一起，
如果结婚了，
那句找到她的现任男友，
看他能不能迁就一下，达成双赢。
代码详细解释：
bool find(int x){
for(int i=head[x];i;i=edge[i].nex){
int y=edge[i].to;
if(!vis[y]){//如果还没有尝试去追求过
vis[y]=1;//标记一下
if(!match[y]||find(match[y])) {//如果目标还没有配偶或者他的配偶还可以将就,并且再返回时因为现在的配偶已经被标记，就不会陷入死循环啦~
match[y]=x;//在一起（爱心）
return true;//配对成功
}
}
}
return false;//所有喜欢的人都不行，配对失败
}
这种没有节操，却又合乎情理的方法，就叫匈牙利算法。
