[BOJ 2051] 최소 버텍스 커버

문제

---

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

풀이

---

minimal vertex cover를 직접 구하는 문제이다.

구하는 과정은 Kőnig’s Theorem의 증명 과정을 참고했다.

결론만 얘기하자면 최대 매칭을 구했을 때, minimal vertex cover는 다음 노드들로 구성된다.

• 왼쪽 노드 중 최대 매칭에 포함되지 않는 노드

• 이 노드들에서 시작해서, alternating path를 통해 도달할 수 있는 오른쪽 노드

여기서 alternating path란, 최대 매칭에 포함되지 않는 노드에서 출발하여, 최대 매칭에 속하지 않는 엣지, 최대 매칭에 속하는 엣지를 번갈아 선택하는 경로이다.

코드

---

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])):
            a[cur] = nxt
            b[nxt] = cur
            return 1
    return 0


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

for i in range(1, n + 1):
    data = list(map(int, sys.stdin.readline().split()))
    for j in range(1, data[0] + 1):
        graph[i].append(data[j])

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

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

left = [0] * (n + 1)
right = [0] * (m + 1)

queue = []
for i in range(1, n + 1):
    if not a[i]:
        queue.append((i, 0))
        left[i] = 1

while queue:
    cur, flag = queue.pop()
    
    if flag:
        nxt = b[cur]
        if not left[nxt]:
            left[nxt] = 1
            queue.append((nxt, 0))
    else:
        for nxt in graph[cur]:
            if not right[nxt] and a[cur] != nxt:
                right[nxt] = 1
                queue.append((nxt, 1))

print(ans)
res_left = []
res_right = []

for i in range(1, n + 1):
    if not left[i]:
        res_left.append(i)

for j in range(1, m + 1):
    if right[j]:
        res_right.append(j)


print(len(res_left), *res_left)
print(len(res_right), *res_right)