[2252] 줄 세우기

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

2252번: 줄 세우기

<문제>

입력은 노드의 개수, 간선의 개수와 방향그래프가 들어온다.

a가 b보다 키가 크고, b가 c보다 키가 큰데 c가 a보다 키가 클수는 없다. 

한마디로 입력은 곧 DAG이고, 위상정렬을 사용할 전제조건이 충족된 셈이다.

 

이후로는, 그냥 위상정렬을 해주어 출력하면 된다.

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
 
int n, m;
vector<int>adj[32001];
int a[32001];
int d[32001];
bool check[32001];
int main(void) {
    int i, j, cur = 0, cnt = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        d[y]++;
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (d[j] == 0 && check[j] == false) {
                cur = j;
                cnt++;
                break;
            }    
        }
        a[cnt] = cur;
        check[cur] = true;
        for (auto x : adj[cur]) {
            d[x]--;
        }
    }
    for (i = 1; i <= n; i++)
        printf("%d ", a[i]);
    return 0;
}