[백준BOJ] 1298 노트북의 주인을 찾아서

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

1298번: 노트북의 주인을 찾아서

---

문제해설

각 시작 노드 ( 사람 ) 에서

노트북 주인이 없다면 flow를 발생시켜서

노트북을 갖게 하면 됩니다.

---

전체코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------

#define MAX_N 101

vector<int> map[MAX_N];
int occupy[MAX_N];
int occupied[MAX_N];
bool visit[MAX_N];
bool dfs(int x) {
	visit[x] = true;
	for (int i = 0; i < map[x].size(); i++) {
		int y = map[x][i];
		if (occupied[y] == -1 || (!visit[occupied[y]] && dfs(occupied[y]))) {
			occupy[x] = y;
			occupied[y] = x;
			return true;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N, M; cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		map[a].push_back(b);
	}
	memset(occupy, -1, sizeof(occupy));
	memset(occupied, -1, sizeof(occupied));
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (occupy[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (dfs(i)) ans++;
		}
	}
	cout << ans << endl;
}

---

기타