易错警示:
数组大小问题:使用领接表存储图,需要另e,ne数组的大小为100010。特别是e数组!
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
int e[M], ne[M], h[N], idx;
int match[N];
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]) {
if (!st[e[i]]) {
st[e[i]] = true;
if (!match[e[i]]) {
match[e[i]] = x;
return true;
}
else if (match[e[i]] && find(match[e[i]])) {
match[e[i]] = x;
return true;
}
}
}
return false;
}
int main() {
memset(h, -1, sizeof h);
int n1, n2, m;
cin >> n1 >> n2 >> m;
while (m--) {
int u, v;
cin >> u >> v;
add(u, v);
}
int res = 0;
for (int i = 1; i <= n1; i++) {
memset(st, false, sizeof st);
if (find(i)) res++;
}
cout << res;
return 0;
}