1733번: 등번호

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

각 참가자마다 두 번호와 간선을 만들어 이분 그래프를 만든다.
이분 매칭을 해서 매칭 수가 n보다 작으면 불가능하고 n이면 각 참가자마다 매치된 번호를 출력한다.

Edmonds-Karp Algorithm을 사용하는 경우에는 visited 체크를 위해 배열을 초기화하는 대신에 탐색마다 다른 수를 덮어 씌어 TLE을 피해야 한다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<vector>
using namespace std;
const int MX = 1e6;
int n, r, vis[MX + 1], rev[MX + 1], mc[MX + 1], cnt;
vector<int> adj[MX + 1];
int dfs(int h) {
    if (vis[h] == cnt) return 0;
    vis[h] = cnt;
    for (int it : adj[h]) if (!rev[it] || dfs(rev[it])) {
        mc[h] = it;
        rev[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) scanf("%d%d", &x, &y), adj[i] = { x,y };
    for (int i = 1; i <= n; i++) ++cnt, r += dfs(i);
    if (r < n) puts("-1");
    else for (int i = 1; i <= n; i++) printf("%d\n", mc[i]);
    return 0;
}

매칭을 빠르게 구하기 위해 Hopcorft-Karp 알고리즘을 쓴다.
시간복잡도는 $O(n\sqrt n)$

#include<cstdio>
#include<vector>
using namespace std;
const int MX = 1e6;
int n, mc[MX + 1], lv[MX + 1], rev[MX + 1], q[MX], r;
vector<int> adj[MX + 1];
int bfs() {
    int flag = 0, h = 0, t = 0;
    for (int i = 1; i <= n; i++) {
        if (!mc[i]) q[t++] = i, lv[i] = 0;
        else lv[i] = -1;
    }
    for (; h < t; h++) for (int it : adj[q[h]]) {
        if (!rev[it]) flag = 1;
        else if (!~lv[rev[it]]) lv[rev[it]] = lv[q[h]] + 1, q[t++] = rev[it];
    }
    return flag;
}
int dfs(int h) {
    for (int it : adj[h]) if (!rev[it] || lv[h] < lv[rev[it]] && dfs(rev[it])) {
        mc[h] = it;
        rev[it] = h;
        return 1;
    }
    lv[h] = 0;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) scanf("%d%d", &x, &y), adj[i] = { x,y };
    while (bfs()) for (int i = 1; i <= n; i++) if (!mc[i]) r += dfs(i);
    if (r < n) puts("-1");
    else for (int i = 1; i <= n; i++) printf("%d\n", mc[i]);
    return 0;
}