FMATCH - Fast Maximum Matching
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
const int N = 50000, INF = 1e9;
int mx[N], my[N], d[N], nx, ny;
vector<int> g[N];
void enter() {
int m; cin >> nx >> ny >> m;
for(int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
g[u-1].push_back(v-1);
}
}
bool dfs(int u, int mind) {
for (int v : g[u]) if(my[v] == -1 ? d[u] == mind : d[my[v]] == d[u]+1 && dfs(my[v], mind)) return mx[u] = v, my[v] = u, true;
d[u] = INF;
return false;
}
int maxMatch() {
int matching = 0;
fill(mx, mx + nx, -1); fill(my, my + ny, -1);
while(true) {
fill(d, d + nx, INF); queue<int> q;
for(int u = 0; u < nx; ++u) if(mx[u] == -1) d[u] = 0, q.push(u);
int mind = INF;
while(!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) if(my[v] == -1) mind = min(mind, d[u]);
else if(d[my[v]] == INF) d[my[v]] = d[u]+1, q.push(my[v]);
}
if(mind == INF) break;
for(int u = 0; u < nx; ++u) if(d[u] > mind) d[u] = INF;
for(int u = 0; u < nx; ++u)
if(mx[u] == -1 && dfs(u, mind)) ++matching;
}
return matching;
}
int main() {
ios::sync_with_stdio(false);
enter();
cout << maxMatch() << endl;
return 0;
}