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;
}

Download