#BOJ2188

축사 배정

이분 매칭 알고리즘에 대해서 공부해보려고 생각하고 있었는데 이걸 활용할 때 DFS를 활용하기 때문에 스터디 주제로 들고가기 좋을 것 같아서 준비해 보았다. 이분 매칭 자체가 DFS를 활용해서 분배하는 알고리즘이기 때문에 이번 시간에 가져왔다. 다만, 아주 쉬운 개념은 아니어서 현재 보고 있는 책의 저자의 영상을 참고하였다. DFS를 이용해서 재귀적으로 계속해서 매칭 시켜주는 코드를 통해서 이분 매칭이 실현 될 수 있게 하였다.

import sys

def dfs(x):
    for now in cow[x]:
        if home[now]:
            continue
        home[now] = True

        if d[now] == -1 or dfs(d[now]):
            d[now] = x
            return True
    return False

N, M = map(int, sys.stdin.readline().split())

cow = [[] for _ in range(N)]
d = [-1] * M

ans = 0

for i in range(N):
    x = list(map(int, sys.stdin.readline().split()))
    for j in x[1:]:
        j -= 1
        cow[i].append(j)

for i in range(N):
    home = [False] * M
    if dfs(i):
        ans += 1

print(ans)