이분 매칭(Bipartite Matching)

// 이분매칭은 네트워크플로우에 연결되는 개념
// DFS를 이용해서 집단과 집단간의 매칭이 "조건대로" + 최대한 이루어지도록 하는 개념

// Max Matching 이라고도 함
// 각 정점을 연결하고, start, end 정점을 각각 만들어서 집단별로 연결시킨 후에
// 그 간선의 유량을 1로 설정하면 네트워크플로우의 개념으로 적용가능

#include <iostream>
#include <vector>
using namespace std;

#define MAX 100

vector<int> a[MAX];
int d[MAX]; // 특정 정점을 가리키고 있는 정보를 표현
bool c[MAX]; // 정점의 처리 여부

bool dfs(int x) { // matching 이 가능한지 여부를 판단하기 위해 bool type을 사용

	// 연결된 모든 노드에 대해서 들어갈 수 있는지 시도해본다
	for (int i = 0; i < a[x].size(); i++) {
		int t = a[x][i];

		// 이미 처리된 노드는 더이상 볼 필요가 없음
		if (c[t]) continue;
		c[t] = true;

		// 비어있거나 점유노드가 다른 곳에 매칭될 수 있는 경우
		if (d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}

	return false;
}

int main() {
	int answer = 0; // answer 는 이분매칭을 통해 최대한 만족하는 매칭의 갯수를 의미

	for (int i = 1; i <= MAX; i++) {
		fill(c, c + MAX, false); // 매 탐색마다 처리된 노드를 초기화해줌
		if (dfs(i)) answer++;
	}
}