AcWing 861. 二分图的最大匹配
原题链接
简单
作者:
qgc123
,
2021-12-05 23:30:12
,
所有人可见
,
阅读 174
#include<iostream>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
unordered_map<int, vector<int>> mp;
const int N = 200005;
int st[N];
int res[N];
int func(int u)
{
st[u] = 1;
for(auto i : mp [u])
{
if (!st[i])
{
st[i] = 1;
if (res[i] == 0 || func(res[i]))
{
res[i] = u;
return 1;
}
}
}
return 0;
}
int main()
{
int n1, n2, m;
cin >> n1 >> n2 >> m;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
mp[a].push_back(b);
}
int ans = 0;
for (int i = 1; i <= n1; i++)
{
memset(st, 0, sizeof st);
ans+=func(i);
}
cout << ans;
}