NKBM - Cặp ghép cực đại trên đồ thị hai phía
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define mset(a,i) memset(a, i, sizeof a)
const int N = 1000;
int nx, ny, my[N], vy[N];
vector<int> g[N];
void enter() {
cin >> nx >> ny; int m; cin >> m;
for(int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
g[u-1].push_back(v-1);
}
}
bool dfs(int s) {
TR(g[s], u) if(!vy[*u]) {
vy[*u] = true;
if(my[*u] == -1 || dfs(my[*u])) return my[*u] = s, true;
}
return false;
}
int maxMatch() {
mset(my, -1); int res = 0;
for(int i = 0; mset(vy, 0), i < nx; ++i) if(dfs(i)) ++res;
return res;
}
int main() {
ios::sync_with_stdio(false);
enter();
cout << maxMatch() << '\n';
return 0;
}