이분 매칭

이분매칭은 x -> y로 가는 y를 모든 x에 대하여 선택할 때 두개 이상의 x가 y로 매칭되지 않으면서 최대로 선택할 수 있는 알고리즘입니다.

dfs와 bfs로 접근 가능하며 BFS는 잘 알려진 네트워크 플로우가 속합니다.

본 글에서는 DFS를 사용하여 경우의 수를 찾아보겠습니다.

이분 매칭의 메인 아이디어는 모든 x에 대하여 선택 가능한 y를 찾아 가면서,

1. x가 탐색 중 만난 y가 이전에 다른 x에게 선택되어 지지 않았거나,

2. x가 y를 선택할 때, y를 선택했던 x가 다른 y를 선택할 수 있으면, (즉, {x,y} 상태에서, {x,y}, {x,y} 쌍이 구성될 수 있다면)

이 외의 경우는 x의 짝은 존재 하지 않는다.

현재 탐색하고자 하는 x 는 쌍을 구성할 수 있습니다.

두개의 배열을 선언하는데 하나는 y를 선택한 x의 정보를 저장하는 배열 match와 방문체크 visit 배열입니다.

열혈강호 1, 노트북 주인을 찾아서

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
typedef long long ll;

int n, m;
int ma[101] = { 0, };
vector<int> v[101];
bool visit[101] = { 0, };
bool dfs(int node) {
	if (visit[node]) return false;
	visit[node] = true;
	for (auto nxt : v[node]) {
		if (!ma[nxt] || dfs(ma[nxt])) {
			ma[nxt]= node;
			return true;
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		memset(visit, 0, sizeof(visit));
		if (dfs(i)) {
			ans += 1;
		}
	}
	cout << ans;
}