[1733번] 등번호

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭

다음 링크를 확인하고 이 문제를 풀자.

이분 매칭(Bipartite Matching) 시간 단축 방법 :: http://www.crocus.co.kr/744

그리고 이분 매칭으로 문제를 해결하자.

이 문제를 검색하여 들어온 분들이라면, 이분 매칭을 몰라서 들어온 것이 아닌, 

어떤 알고리즘으로 이 문제의 TLE를 벗어나야 하나에 대해 고민하다 왔을 것이다.

세상에는 이분 매칭에 대한 시간 복잡도가 빠른 알고리즘이 많지만, 

가장 기본적인 이분 매칭 알고리즘에서 1개만 변화시켜도 AC를 받을 수 있을 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 1000001
 
using namespace std;
 
int n;
int adj[MAX_N][2];
int aMatch[MAX_N];
int bMatch[MAX_N];
int visit[MAX_N];
int visitCnt = 1;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
 
    for (int next = 0; next < 2; next++)
    {
        if (adj[a][next])
        {
            int b = adj[a][next];
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                aMatch[a] = b;
                bMatch[b] = a;
 
                return true;
            }
        }
    }
 
    return false;
}
 
int bipartiteMatch()
{
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    int size = 0;
 
    for (int start = 0; start < n; start++)
    {
        visitCnt++;        
        size += dfs(start);
    }
 
    return size;
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int front, back;
        scanf("%d %d", &front, &back);
        
        adj[i][0] = front;
        adj[i][1] = back;
    }
 
    int ans = bipartiteMatch();
 
    if (ans != n)
        printf("-1");
 
    else
        for (int i = 0; i < n; i++)
            printf("%d\n", aMatch[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>