2051번: 최소 버텍스 커버

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

$O(n^2m)$

#include<cstdio>
#include<vector>
using namespace std;
int n, m, r[1001], vis[1001], res, ck[1001], acnt, bcnt, b[1001];
vector<int> adj[1001];
int f(int h) {
    if (vis[h]) return 0;
    vis[h] = 1;
    for (int it : adj[h]) {
        if (!r[it] || f(r[it])) {
            r[it] = h;
            return 1;
        }
    }
    return 0;
}
void g(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    acnt++;
    for (int it : adj[h]) bcnt += !b[it]++, g(r[it]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= n; i++)
        for (scanf("%d", &x); x--;) scanf("%d", &y), adj[i].push_back(y);
    for (int i = 1; i <= n; i++) {
        if (f(i)) ck[i] = 1, res++;
        for (int j = 1; j <= n; j++) vis[j] = 0;
    }
    for (int i = 1; i <= n; i++) if (!ck[i]) g(i);
    printf("%d\n%d", res, n - acnt);
    for (int i = 1; i <= n; i++) if (!vis[i]) printf(" %d", i);
    printf("\n%d", bcnt);
    for (int i = 1; i <= n; i++) if (b[i]) printf(" %d", i);
    return 0;
}