[BOJ 1867] 돌멩이 제거

문제

---

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

풀이

---

이분 그래프에서 maximum matching의 크기와 minimum vertex cover의 크기가 같다는 Kőnig’s Theorem을 이용하면 쉽게 풀린다.

왼쪽에 x좌표를 의미하는 1~n을 놓고, 오른쪽에 y좌표를 의미하는 1~n을 놓자.

(c, d) 위의 돌멩이는 x=c를 훑거나, y=d를 훑으면 치워진다.

그러므로 (c, d) 엣지를 이어주면, vertex cover를 만들었을 때 돌멩이가 치워지게 된다.

코드

---

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)