[알고리즘 정리] 이분 매칭

이분 매칭

시간 복잡도 : O(E*sqrt(V))

visit : 방문 여부 확인

bs : 현재 노드가 연결된 노드

ex) bs[a]=b; 라면, a와 b가 연결된 상태이다.

기본 코드

bool dfs(int cur) 
{
	if (visite[cur])
		return 0;
	visite[cur] = 1;
	for (int i = 0; i < node[cur].size(); i++) 
	{
		int next = node[cur][i];
		if (!bs[next] || dfs(bs[next])) 
		{
			bs[next] = cur;
			return 1;
		}
	}
	return 0;
}

int binary_match() 
{
	int ret = 0;
	for (int i = 1; i <= n; i++) 
	{
		fill_n(&visite[0], MAX, 0);
		if (dfs(i))ret++;
	}
	return ret;
}

기본 예제

https://www.acmicpc.net/problem/1298

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 5005
#define INF 987654321
#define MOD 31991
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n, m, bs[MAX];
bool visite[MAX];
vector<vector<int>> node;

bool dfs(int cur) 
{
	if (visite[cur])
		return 0;
	visite[cur] = 1;
	for (int i = 0; i < node[cur].size(); i++) 
	{
		int next = node[cur][i];
		if (!bs[next] || dfs(bs[next])) 
		{
			bs[next] = cur;
			return 1;
		}
	}
	return 0;
}

int binary_match() 
{
	int ret = 0;
	for (int i = 1; i <= n; i++) 
	{
		fill_n(&visite[0], MAX, 0);
		if (dfs(i))ret++;
	}
	return ret;
}

int main()
{
	scanf("%d %d", &n, &m);
	node.resize(n + 1);
	for (int i = 1; i <= m; i++) 
	{
		int a, b;
		scanf("%d%d", &a,&b);
		node[a].push_back(b);
	}
	printf("%d", binary_match());
	return 0;
}