BOJ)1733 등번호

문제: icpc.me/1733

참가자와 등번호들로 이루어진 이분 그래프를 이분매칭하는 문제이다.

이분 매칭의 역추적은 매칭을 시킬 때 배열등에 저장하여 쉽게 할 수 있다.

다만 N이 100만이므로 매칭때마다 memset을 사용할 경우 TL을 볼 수도 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> vt;
int check[1000100];
int backmatch[1000100];
int r[1000100];
int n, x, y, s;
bool dfs(int here) {
    if (here == -1) return true;
    for (int next : vt[here]) {
        if (check[next] == s)continue;
        check[next] = s;
        if (dfs(backmatch[next])) {
            backmatch[next] = here;
            r[here] = next;
            return true;
        }
    }
    return false;
}
int bmatch() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        s = i;
        if (dfs(i))
            ret++;
    }
    return ret;
}
 
int main()
{
    scanf("%d", &n);
    vt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        vt[i].push_back(x);
        vt[i].push_back(y);
    }
    memset(backmatch, -1, sizeof(backmatch));
    int res = bmatch();
    if (res != n)
        printf("-1\n");
    else {
        for (int i = 1; i <= n; i++)
            printf("%d\n", r[i]);
    }
    return 0;
}