AcWing 861. 二分图的最大匹配
原题链接
简单
作者:
梦都会空
,
2021-12-06 18:16:10
,
所有人可见
,
阅读 160
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1000010;
int n1,n2,m;
int head[N],e[N],en[N],idx;
int a[N];
bool st[N];
void add(int x,int y)
{
e[idx]=y;
en[idx]=head[x];
head[x]=idx++;
}
int find(int x)
{
for(int i=head[x]; i != -1;i=en[i])
{
int j=e[i];
if(!st[j])
{
st[j]=true;
if(a[j]==0||find(a[j]))
{
a[j] = x;
return 1;
}
}
}
return 0;
}
signed main()
{
cin>>n1>>n2>>m;
memset(head, -1, sizeof head);
while (m -- )
{
int a,b;
scanf("%d%d", &a, &b);
add(a, b);
}
int sum=0;
for(int i=1;i<=n1;i++)
{
memset(st, false, sizeof st);
if(find(i)) sum++;
}
printf("%d\n",sum);
return 0;
}