최소 버텍스 커버

• 이분 그래프에서 최소 버텍스 커버를 구하는 문제.
• 이분 그래프에서 최대 매칭의 크기와 최소 버텍스 커버의 크기가 같다는 쾨닉의 정리는 많이 쓰이지만, 최소 버텍스 커버의 원소들을 실제로 구하는 것이 필요한 문제는 흔하지는 않다.. 최소 버텍스 커버 원소들을 구하는 방법은 최소 버텍스 커버 구하기 참고
• 시간복잡도는 이분매칭에 O(VE), 그리고 그 결과를 이용해서 최소 버텍스 커버를 구하는 데에 다시 O(VE)가 든다. 총 O(VE).

"""Solution code for "BOJ 2051. 최소 버텍스 커버".

- Problem link: https://www.acmicpc.net/problem/2051
- Solution link: http://www.teferi.net/ps/problems/boj/2051

Tags: [Bipartite Matching]
"""

from teflib import tgraph


def minimum_vertex_cover(bigraph):

    def dfs_rec(u, is_mvc):
        is_mvc[u] = False
        for v in bigraph[u]:
            if not is_mvc[v]:
                is_mvc[v] = True
                if (next_u := matched_node[v]) is not None and is_mvc[next_u]:
                    dfs_rec(next_u, is_mvc)

    matching = tgraph.bipartite_matching(bigraph)
    matched_node = [None] * len(bigraph)
    for u, v in matching.items():
        matched_node[v] = u
    is_mvc = [bool(edges) for edges in bigraph]
    for u, edges in enumerate(bigraph):
        if edges and u not in matching:
            dfs_rec(u, is_mvc)
    return [u for u, u_is_mvc in enumerate(is_mvc) if u_is_mvc]


def main():
    N, M = [int(x) for x in input().split()]
    bigraph = [[] for _ in range(N + M)]
    for i in range(N):
        _, *j = [int(x) for x in input().split()]
        bigraph[i] = [x + N - 1 for x in j]

    mvc = minimum_vertex_cover(bigraph)
    answer1 = [u + 1 for u in mvc if bigraph[u]]
    answer2 = [v - N + 1 for v in mvc if not bigraph[v]]

    print(len(mvc))
    print(len(answer1), *answer1)
    print(len(answer2), *answer2)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.bipartite_matching