BOJ 14864 줄서기

줄서기

(http://boj.kr/14864)

먼저, 카드를 순서대로 1, 2, 3, 4, 5, … 순서로 준다고 가정한다.

그러면 모두가 자신의 왼쪽보다는 크고 오른쪽보다는 작은 상황이 된다.

이 상황에서 (a, b)라는 입력이 들어오면, b가 a보다 작아야 한다는 것이 된다.

입력이 올바르다는 가정 하에, b를 1 줄이고 a를 1 늘리며 번호를 완성해갈 수 있다.

입력이 올바르지 않다면 위의 과정을 반복했을 때 모순된 결과가 나오게 된다.

#include <bits/stdc++.h>
 
int cnt[100001];
bool chk[100001];
 
int main() {
    int n, m, u, v;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 1;i <= n;++i)
        cnt[i] = i;
 
    for (int i = 0;i < m;++i) {
        scanf("%d %d", &u, &v);
        cnt[u]++;
        cnt[v]--;
    }
 
    for (int i = 1;i <= n;++i) {
        if (cnt[i] < 1 || cnt[i] > n || chk[cnt[i]] == true) {
            printf("-1");
 
            return 0;
        }
        chk[cnt[i]] = true;
    }
 
    for (int i = 1;i <= n;++i)
        printf("%d ", cnt[i]);
 
    return 0;
}