import sys
input = sys.stdin.readline
def DFS(now):
for w in graph[now]:
if visited[w]:
continue
visited[w] = 1
if work[w]>=0:
DFS(work[w])
if work[w]<0:
work[w] = now
work[man[now]] = -1
man[now] = w
return
N,M = map(int,input().split())
graph = [[*map(int,input().split())][1:] for i in range(N)]
cnt = 0; man = [0]*N; work = [-1]*(M+1)
for i in range(N):
visited = [0]*(M+1)
DFS(i)
print(N-man.count(0))
이분매칭 알고리즘 기본문제이다.
알고리즘은 https://yjg-lab.tistory.com/209 이곳을 참고하였다.
오늘의 교훈) 다양한 이분매칭 응용문제를 풀어보자