FMATCH - Fast Maximum Matching
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct HopcroftKarp
{
vector <int> leftMatch, rightMatch, dist, cur;
vector < vector <int> > a;
int m, n;
HopcroftKarp() {}
HopcroftKarp(int _m, int _n)
{
m = _m; n = _n;
a = vector < vector <int> >(m);
leftMatch = vector <int>(n, -1);
rightMatch = vector <int>(m, -1);
dist = vector <int>(m, -1);
cur = vector <int>(m, -1);
}
void addEdge(int x, int y)
{
a[x].push_back(y);
}
int bfs()
{
int found = 0;
queue <int> q;
for (int i = 0; i < m; i++)
if (rightMatch[i] < 0) dist[i] = 0, q.push(i);
else dist[i] = -1;
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = 0; i < int(a[x].size()); i++)
{
int y = a[x][i];
if (leftMatch[y] < 0) found = 1;
else
if (dist[leftMatch[y]] < 0)
dist[leftMatch[y]] = dist[x] + 1, q.push(leftMatch[y]);
}
}
return found;
}
int dfs(int x)
{
for (; cur[x] < int(a[x].size()); cur[x]++)
{
int y = a[x][cur[x]];
if (leftMatch[y] < 0 || (dist[leftMatch[y]] == dist[x] + 1 && dfs(leftMatch[y])))
{
leftMatch[y] = x; rightMatch[x] = y;
return 1;
}
}
return 0;
}
int maxMatching()
{
int match = 0;
while (bfs())
{
for (int i = 0; i < m; i++) cur[i] = 0;
for (int i = 0; i < m; i++)
if (rightMatch[i] < 0) match += dfs(i);
}
return match;
}
};
int main()
{
int m, n, edge, x, y;
cin >> m >> n >> edge;
HopcroftKarp u(m, n);
while (edge--) scanf("%d%d", &x, &y), u.addEdge(--x, --y);
cout << u.maxMatching() << endl;
}