NKBM - Cặp ghép cực đại trên đồ thị hai phía
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
using namespace std;
int m, n, sc;
bool a[1111][1111], vs[1111];
int x[1111], y[1111];
bool tim(int i) {
if(vs[i]) return false;
vs[i] = true;
for(int j=1;j<=n;++j) if(a[i][j]) {
if(y[j]==0) {
x[i] = j;
y[j] = i;
return true;
}
if(tim(y[j])) {
x[i] = j;
y[j] = i;
return true;
}
}
return false;
}
int main() {
int u, v, socap=0;
scanf("%d%d%d", &m, &n, &sc);
for(int i=0;i<sc;++i) {
scanf("%d%d", &u, &v);
a[u][v] = true;
}
for(int i=1;i<=m;++i) {
memset( vs, 0, sizeof(vs));
if(tim(i)) ++socap;
}
cout << socap << endl;
//system("pause");
return 0;
}