https://www.acmicpc.net/problem/11376
시간 4초, 메모리 256MB

input :

• N M (1 ≤ N, M ≤ 1,000)
• i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호

output :

• 강호네 회사에서 할 수 있는 최대의 일의 개수를 출력

조건 :

• 직원은 1번부터 N번까지, 일은 1번부터 M번까지 번호가 매겨져 있다.

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

---

과거 풀었던 BOJ 1671 상어의 저녁식사와 비슷한 문제이다.

다음 풀이

1. 각각의 일은 1명이 담당
2. 최대 2개의 일을 수행.

이분 매칭이란 것은 쉽게 확인할 수 있다.
최대한 많은 일을 하는데 정해진 인원이 있기 때문에 이를 통해 알 수 있다.
최대 2개라는 설명을 통해 모든 인원에 대한 반복문을 2번 수행해야 함을 알 수 있따.

import sys

def main():
    def dfs(node):
        if visit[node] == 1:
            return 0
    
        visit[node] = 1
    
        for key in employee[node]:
            if ans[key] == 0:
                ans[key] = node
                return 1
    
        for key in employee[node]:
            if dfs(ans[key]):
                ans[key] = node
                return 1
    
        return 0
    
    n, m = map(int, sys.stdin.readline().split())
    employee, ans = [[] for _ in range(n + 1)], [0] * (m + 1)
    
    for i in range(1, n + 1):
        temp = list(map(int, sys.stdin.readline().split()))
        employee[i] += temp[1:]
    
    cnt = 0
    for _ in range(2):
        for i in range(n + 1):
            if cnt == m:
                break
    
            visit = [0] * (n + 1)
            if dfs(i):
                cnt += 1
    
    print(cnt)

if __name__ == '__main__':
    main()