[백준] 14864 - 줄서기

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

14864번: 줄서기

 

입력으로 주어지는 쌍들을 이용해서 하나의 그래프를 생성할 수 있다.

그래프가 생성되면 각 정점에 입력 간선, 출력 간선이 생기고 그에 따라 각 학생이 가져야 하는 번호를 유추할 수 있다.

 

각 학생이 가져야 하는 번호를 유추하는 방법은, 해당 학생보다 작은 번호를 가진 학생 수와 큰 번호를 가진 학생 수를 통해서 알 수 있다.

예제 1번의 4번 정점으로 예시를 들면, 입력 간선의 개수는 1개, 출력 간선의 개수는 1개이다.

 

원래대로라면 자신보다 작은 번호를 가진 학생수는 1, 2, 3 총 3명이지만, 입력 간선으로 인해 이전 학생 중에 자신보다 큰 번호를 가진 학생수가 1명 존재하고, 출력 간선으로 인해 이후 학생 중에 자신보다 작은 번호를 가진 학생 수가 1명 존재한다.

따라서 less = out[i] + i - 1 - in[i] 이다.

자신보다 큰 번호를 가진 학생 수도 쉽게 구할 수 있다.

 

#include <iostream>
using namespace std;

int num[100001], in[100001], out[100001], ans[100001];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        out[a]++;
        in[b]++;
    }

    for (int i = 1; i <= n; i++) {
        int less = out[i] + i - 1 - in[i];
        int greater = n - i - out[i] + in[i];
        if (less + greater >= n || num[less + 1]) {
            cout << -1;
            return 0;
        }
        num[less + 1] = 1;
        ans[i] = less + 1;
    }
    
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
}