백준(BOJ) 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]))
		// next노드가 연결되어 지지 않은 상태거나,
		// 연결되었지만 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);
		// 매 노드에서 dfs를 돌리기전에 항상 visite 초기화한다.
		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;
}