알고리즘 문제/백준

[C++] 축사 배정 - 2188

우대비 2022. 12. 1. 21:04
반응형
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 201;

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

bool dfs(int x)
{
	for (int i = 0; i < v[x].size(); i++)
	{
		int s = v[x][i];
        
		if (c[s]) continue;     
		c[s] = true;

		if (d[s] == 0 || dfs(d[s]))
		{
			d[s] = x;
			return true;
		}
	}
	return false;
}

int main()
{
	int N, M;
	cin >> N >> M;

	for (int i = 1; i < N + 1; i++)
	{
		int si, Mn;
		cin >> si;
		for (int j = 0; j < si; j++)
		{
			cin >> Mn;
			v[i].push_back(Mn);
		}
	}
    
	int sum = 0;
	for (int i = 1; i < N + 1; i++)
	{
		fill(c, c + MAX, false);
		if (dfs(i)) sum++;
	}

	cout << sum;
	return 0;
}

 

 

반응형
LIST

'알고리즘 문제 > 백준' 카테고리의 다른 글

[C++] 가운데를 말해요 - 1655  (2) 2022.12.10
[C++] 단어 수학 - 1339  (0) 2022.12.05
[C++] 별자리 만들기 - 4386  (0) 2022.11.29
[C++] 2*n 타일링 2 - 11727  (1) 2022.11.26
[C++] 2*n 타일링 - 11726  (0) 2022.11.26