[BOJ 1298] 노트북의 주인을 찾아서

문제

---

https://www.acmicpc.net/problem/1298

풀이

---

이분 매칭 기본 문제이다.

놀랍게도 돌맹이 제거와 동일한 코드가 통과하는데, 두 티어나 차이 나는 이유는 Kőnig’s Theorem 때문이다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if not b[nxt] or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)

b = [0] * (n + 1)
ans = 0

for i in range(1, n + 1):
    visit = [0] * (n + 1)
    ans += dfs(i)

print(ans)