[백준] 17481 최애 정하기

조용한 5분을 줘

 

문제

흑석이와 상도는 국내 최고의 걸그룹인 CAU(Complete & Awesome Unit)을 좋아한다. CAU에는 흑석이와 상도는 좋아하는 멤버가 각각 여러명 존재한다.

흑석이와 상도는 최고로 좋아하는 멤버인 최애 멤버를 정하고자 한다. 그런데 두 친구가 같은 멤버를 좋아하는 것은 두 친구 간의 우정 때문에 그럴 수 없다고 한다.

따라서 우리는 친구들의 우정을 지키기 위해 최고로 좋아하는 멤버인 최애 멤버 1명을 서로 다른 멤버로 정하고자 한다.

친구들의 우정을 지키기 위한 프로그램을 작성해보자.

입력

첫째 줄에 친구들의 수 N과 걸그룹의 멤버 수 M이 주어진다. (2 ≤ N, M ≤ 1000)

다음 M개 줄에 걸쳐서 걸그룹 멤버의 이름이 각각 주어진다. 걸그룹 멤버의 이름은 영문 대문자로만 이뤄져 있으며, 최대 길이는 100글자이다.

다음 N개 줄에 걸쳐서 친구 별로 좋아하는 멤버 수 K(1 ≤ K ≤ M)와 좋아하는 걸그룹 멤버 이름들이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에는 친구들의 우정을 지킬 수 있는 지 여부를 출력한다.

우정을 지킬 수 없는 경우 두 번째 줄에는 최대한 겹치지 않게 친구들 전체가 좋아할 수 있는 최대 멤버 수를 출력한다.

 

친구들과 걸그룹 멤버들을 각각 다른 그룹으로 놓고, 이분그래프를 생성합니다.

최대매칭을 구하고,

최대매칭수가 친구들의 수보다 작으면 NO와 매칭수를, 같다면 YES를 출력합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int N, M, v[1001], s[1001];
vi adj[1001];
string id[1001];
bool dfs(int t) {
	if (v[t])return 0;
	v[t] = 1;
	for (int r : adj[t]) {
		if (!s[r] || dfs(s[r])) {
			s[r] = t;
			return 1;
		}
	}
	return 0;
}
int main() {
	FAST;
	cin >> N >> M;
	REP(i, M)cin >> id[i];
	int x;
	string str;
	REP(i, N) {
		cin >> x;
		while (x--) {
			cin >> str;
			REP(j, M) {
				if (id[j] == str) {
					adj[i].push_back(j);
					break;
				}
			}
		}
	}
	int cnt = 0;
	REP(i, N) {
		mset(v);
		if (dfs(i)) {
			cnt++;
		}
	}
	if (cnt == N) {
		cout << "YES";
	}
	else
		cout << "NO\n"<< cnt;
}