NKBM - Cặp ghép cực đại trên đồ thị hai phía
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 1010;
using namespace std;
int matchX[N], matchY[N], Q[N], T[N];
int m, n, e;
vector<int> a[N];
int BFS() {
int l = 1, r = 0, i, u, v;
for(i = 1; i <= m; i++)
if (matchX[i] == 0) Q[++r] = i;
for(i = 1; i <= n; i++) T[i] = 0;
while (l <= r) {
u = Q[l++];
for(i = 0; i < a[u].size(); i++) {
v = a[u][i];
if (T[v] == 0) {
T[v] = u;
if (matchY[v] == 0) return v;
else Q[++r] = matchY[v];
}
}
}
return 0;
}
void Enlarge(int y) {
int next, x;
for(; y; y = next) {
x = T[y];
next = matchX[x];
matchX[x] = y;
matchY[y] = x;
}
}
int main() {
scanf("%d %d %d", &m, &n, &e);
int i, u, v;
for(i = 1; i <= e; i++) {
scanf("%d %d", &u, &v);
a[u].push_back(v);
}
while (i = BFS()) Enlarge(i);
int res = 0;
for(i = 1; i <= m; i++) if (matchX[i] != 0) res++;
printf("%d\n", res);
}