13503번: 최소 체인 커버

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

최대 이분 매칭을 구해서 풀 수 있다.

모든 정점 i에 대해 source, sink와 각각 연결된 두 개의 정점 i, i'를 만들고
주어지는 간선 u -> v 마다 만들고 있는 이분 그래프에서 간선 u -> v' 을 추가한다.
이 그래프에서의 매칭을 원래 그래프에서 체인에 속한 간선들과 대응시킬 수 있다.
(체인 수) = n - (체인에 속한 간선 수) 이므로 (최소 체인 수) = n - (최대 매칭 수) 이다.

시간복잡도는 $O(nm)$

#include<cstdio>
#include<vector>
using namespace std;
int n, m, vis[10001], rev[10001], t, res;
vector<int> adj[10001];
int f(int h) {
    vis[h] = t;
    for (auto it : adj[h]) if (!rev[it] || vis[rev[it]] ^ t && f(rev[it])) {
        rev[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
    }
    res = n;
    for (t = 1; t <= n; t++) res -= f(t);
    printf("%d", res);
    return 0;
}