二分图是这样一种图：假设我们有一张图，把它拦腰切一刀，切成两段，每一段的所有节点没有连边。
请看一个典型的二分图。观察可以得到，左面的三个节点属于同一侧，它们没有连边；右面的四个节点也属于一侧，它们没有连边。
这就是二分图。 撒花完结
所谓二分图的最大匹配，就是指对于一个二分图，通过取舍某些边让它的节点两两匹配数达到最大。换句话说，就是搞出最多的一一对应。
用匈牙利算法，dfs遍历图。如果发现dfs到的点以前没有遍历过，则检查：
如果目标还没有跟别人匹配或它的搭档已经跟别人匹配了，则目标跟起始点匹配，并让答案数+1.反之则不变。
放题放代码
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #define size 1010 bool vis[size]; int link[size]; bool mp[size][size]; int n,m,e; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*f; } bool dfs(int x){ for(int i=1;i<=m;++i){ if(mp[x][i]&&!vis[i]){ vis[i]=1; if(!link[i]||dfs(link[i])){ link[i]=x; return 1; } } } return 0; } int ans; int main(){ n=read(),m=read(),e=read(); int from,to; for(int i=1;i<=e;++i){ from=read();to=read(); mp[from][to]=1; } for(int i=1;i<=n;++i){ memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d",ans); return 0; }