[백준 11375번] 열혈강호 (Python3)

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 이곳을 참고하였다.

 

오늘의 교훈) 다양한 이분매칭 응용문제를 풀어보자