[백준] 11375번: 열혈강호

11375번: 열혈강호

 

#include<iostream>
#include<vector>
#define MAX 1001
using namespace std;

int d[MAX];
bool c[MAX];
vector<int>w[MAX];

bool dfs(int x) {
	//연결된 모든 노드에 대해서 들어갈시도
	for (int i = 0;i < w[x].size();i++) {
		int y = w[x][i];
		//이미 처리한 노드는 볼 필요 없다
		if (c[y]) continue;
		c[y] = true;
		//현재 아무도 일을 하지 않았거나 그 일을 선택한 사람이 다른 일을 선택할수있는경우
		if (d[y] == 0 || dfs(d[y])) {
			d[y] = x;
			return true;
		}
	}
	return false;
}

int main() {
	int n, m;
	int work, num,cnt=0;
	cin >> n >> m;

	for (int i = 1;i <= n;i++) {
		cin >> work;
		for (int j = 1;j <= work;j++) {
			cin >> num;
			w[i].push_back(num);
		}
	}

	for (int i = 1;i <= n;i++) {
		fill(c, c + MAX, false);
		if (dfs(i)) cnt++;
	}

	cout << cnt;
}