[백준BOJ] 11375 열혈강호

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

11375번: 열혈강호

---

문제해설

밑의 문제와 동일한 문제입니다( 입력 범위만 살짝 다릅니다 )

2019/10/13 - [알고리즘/BOJ] - [백준BOJ] 2188 축사 배정

[백준BOJ] 2188 축사 배정

 

---

전체코드

#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 1001
vector<int> map[MAX_N];

int cow[MAX_N];
int area[MAX_N];
bool visit[MAX_N];

bool fun(int s) {
	visit[s] = true;
	for (int i = 0; i < map[s].size(); i++) {
		if (area[map[s][i]] == -1 || (!visit[area[map[s][i]]] && fun(area[map[s][i]]))) {
			cow[s] = map[s][i];
			area[map[s][i]] = s;
			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 = 1; i <= N; i++) {
		int s; cin >> s;
		for (int j = 0; j < s; j++) {
			int data; cin >> data;
			map[i].push_back(data);
		}
	}
	memset(cow, -1, sizeof(cow));
	memset(area, -1, sizeof(area));
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (cow[i] == -1) {
			memset(visit, false, sizeof(visit));
			if (fun(i)) ans++;
		}
	}
	cout << ans << endl;
}

---

기타