定义
一张无向图，如果可以将节点分成两个部分，使得两个部分内部没有任何边相连，也就是每条边的端点都分属两个部分，就可以说这张图为二分图。
判定
当且仅当图中不存在长度为奇数的环时，这一张图为二分图。
因为显然每经过一条边都会到达另一个部分，以此类推，经过奇数条边后比不可能还在一开始的部分。
最大匹配
选择一些边，使得任意两条边都没有公共的端点，我们就可以称这些边为图的一组匹配，边数最多的一组我们称为最大匹配。
接下俩我们称被选中的边为匹配边，匹配边的端点为匹配点。如果二分图中存在一条路经连接两个非匹配点，使得匹配边与非匹配边在路径上交替出现，那么可以将此路径称为这组匹配的增广路。
根据定义可知，当我们将增广路上的匹配边变为非匹配边，非匹配边变为匹配边，新的匹配边仍然能够构成一组匹配，并且边数增加了1。
匈牙利算法：
用于计算二分图最大匹配，主要就是找增广路。算法会依次尝试为每一个二分图中的左部点\(x\)寻找一个匹配的右部点\(y\)，流程如下：
从一个左端点出发，一次遍历它的出边，会到达一个点\(y\)，接下来我们就要判断点\(y\)的情况：
1.\(y\)没有匹配点，那么可以将\(y\)d的匹配点变为\(x\)。
2.\(y\)有匹配点\(z\)，但是\(z\)可以寻找到新的匹配点。
对于点\(z\)我们可以重复上诉流程，知道寻找不到匹配点为止。
这样一来，如果一个点变为了匹配点，那么它永远不会变回非匹配点，即代表着，假如一个新的点变为了匹配点，那么总的匹配点数量肯定可以增加。
代码实现：模板题：P3386 【模板】二分图最大匹配
#include<algorithm>
#include<stdio.h>
#include<queue>
#define maxn 1005
#define maxm 100005
using namespace std;
int n1,n2,m;
int head[maxn],to[maxm],nex[maxm],m1;
void add(int u,int v) {
to[++m1]=v;
nex[m1]=head[u];
head[u]=m1;
}
int vis[maxn],match[maxn];
bool dfs(int now) {
for(int i=head[now];i;i=nex[i]) {
int st=to[i];
if(!vis[st]) {
vis[st]=1;
if(!match[st] || dfs(match[st])) {
match[st]=now; return true;
}
}
}
return false;
}
int main() {
// freopen("P3386.in","r",stdin);
// freopen("P3386.out","w",stdout);
scanf("%d%d%d",&n1,&n2,&m);
for(int i=1;i<=m;i++) {
int u,v; scanf("%d%d",&u,&v);
add(u,v+n1),add(v+n1,u);
}
int ans=0;
for(int i=1;i<=n1;i++) {
for(int j=1;j<=n2+n1;j++) {
vis[j]=0;
}
if(dfs(i)) ans++;
}
printf("%d\n",ans);
return 0;
}