import sys
def input(): return map(int,sys.stdin.readline().split())
def DFS(i):
if visited[i]:
return
visited[i] = 1
for j in graph[i]:
if not match[j]:
match[j] = i
return 1
for j in graph[i]:
if DFS(match[j]):
match[j] = i
return 1
N,M = input()
graph = [[] for i in range(N+1)]
for _ in range(M):
a,b = input()
graph[a].append(b)
match = [0]*(N+1)
for i in range(1,N+1):
visited = [0]*(N+1)
DFS(i)
print(N+1-match.count(0))
이분매칭 응용문제이자 콰닉의 정리 연습문제
콰닉의 정리에 대한 이론은 https://gazelle-and-cs.tistory.com/12 을 참고하였다.
풀이를 설명하면,
1. 그래프를 가로줄-세로줄을 노드로 하는 이분그래프라고 가정한다.
2. 돌멩이가 있는 위치가 곧 간선이다.
3. 이분매칭을 이용하여 최대매칭 개수를 찾으면, 콰닉의 정리에 따라 그 값이 곧 최소커버노드 개수이다.
콰닉의 정리를 공부할 수 있는 좋은 문제였다.
오늘의 교훈) 이분매칭과 콰닉의 정리를 활용해 다양한 문제를 해결하자