1867번: 돌멩이 제거

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


$O(nk)$

(x,y)가 1일 떄 x->y 간선을 만들어 보면 이분 그래프를 만들 수 있으며 이 그래프에서 minimum vertex cover의 개수가 문제의 답이 된다.
이 수는 쾨닉의 정리에 따라 최대 이분 매칭 수와 같다.

#include<cstdio>
#include<vector>
using namespace std;
int n, k, p[501], vis[501], r;
vector<int> adj[501];
int dfs(int h) {
    if (!vis[h]) {
        vis[h] = 1;
        for (auto it : adj[h]) if (!p[it] || dfs(p[it])) {
            p[it] = h;
            return 1;
        }
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0, x, y; i < k; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) vis[j] = 0;
        r += dfs(i);
    }
    printf("%d", r);
    return 0;
}