====== 최소 버텍스 커버 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:tgraph#bipartite_matching|teflib.tgraph.bipartite_matching]]

{{tag>BOJ ps:problems:boj:플래티넘_2}}