861二分图的最大匹配
作者:
一吱小晨
,
2022-10-31 23:28:11
,
所有人可见
,
阅读 171
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N]; //存着当前匹配的数据,比如两个集合,n1表示下标,match[]存的数是n2集合中与n1配对的数
bool st[N]; //表示已经是否被遍历过
void add (int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool find(int x){
for (int i = h[x]; i != -1; i = ne[i]){ //邻接表进行寻找
int j = e[i]; //与当前n1集合中相连的j元素(j是n2集合中的)
if (!st[j]){
st[j] = true; //标为已经配对
if (match[j] == 0 || find(match[j])){ //如果没有配对,或者已经有配对但是能找到另一个配对
match[j] = x;
return true;
}
}
}
return false;
}
int main(){
cin >> n1 >> n2 >> m;
memset (h, -1, sizeof h);
for (int i = 0; i < m; i ++){
int a, b;
cin >> a >> b;
add (a, b);
}
int res = 0; //用来记录配对的个数
for (int i = 1; i <= n1; i ++){
memset (st, false, sizeof st);
if (find(i)) res ++; //如果可以成功进行配对,就让res ++
}
cout << res << endl;
return 0;
}