#include<iostream> #include<cstdio> #include<cstdlib> #define maxn 20010 using namespace std; int n,m,e,u,v,ans=0; int mp[maxn][maxn],match[maxn];//eg:match[i]=k意为用右面的点i去匹配左面的点k bool visit[maxn]; bool dfs(int u){ for(int v=1;v<=m;v++){ if(visit[v]==true||(!mp[u][v])) continue;//如果这个点被标记过了或根本没有这条边就跳过 visit[v]=true; //打标记来判环 if(match[v]==0||dfs(match[v])){ match[v]=u;// 如果搜到右边的点就直接跳回左边 return true; } } return false; } int main(){ cin>>n>>m>>e; for(int i=1;i<=e;i++){ cin>>u>>v; mp[u][v]=1; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) visit[j]=false;//每次使用的时候清空判环+记录匹配的边的数组,保证每次走的都是非匹配边 ans+=dfs(i); } cout<<ans<<endl; return 0; }
原文:https://www.cnblogs.com/DReamLion/p/14394541.html