띠그랭

열혈강호 11375번 - 이분매칭

문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

예제 입력

 
xxxxxxxxxx
5 5
2 1 2
1 1
2 2 3
3 3 4 5
1 1

예제 출력

 
xxxxxxxxxx
4

소스 코드

 
x
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int emp;    // 일하는 사람 수
int work;   // 작업의 수
int res;    // 결과
vector<vector<int>> v(1001);    // 어떤 사람이 무슨 일 할 수 있는지 저장
int visit[1001];        // i번째 사람의 이미 방문했는지 check
int match[1001];        // i번째 일을 누가 했는지 match[i]에 저장
​
int dfs(int person)
{
    if (visit[person]) return 0;        // 이미 dfs돌았다면 패스
    visit[person] = 1;
    
    for (int i = 0; i < v[person].size(); i++)
    {
        int here_work = v[person][i];       // 직원이 무슨 일 할 수 있는지 here_work에 저장
        if (!match[here_work] || dfs(match[here_work]))
        {
            match[here_work] = person;      // 그 작업을 현재 사람에게 매칭
            return 1;
        }
    }
    return 0;
}
​
int main()
{
    cin >> emp >> work;
    for (int i = 1; i <= emp; i++)
    {
        int seq;
        cin >> seq;
        for (int j = 1; j <= seq; j++)
        {
            int tmp;
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }
    for (int i = 1; i <= emp; i++)
    {
        fill(visit, visit + emp, 0);
        if (dfs(i)) res++;
    }
​
    cout << res << '\n';
​
    return 0;
}