백준[1766] 문제집

문제 설명

풀이

위상 정렬을 이용하여 풀이할 수 있다. 위상 정렬을 이용하는 과정에서 더 쉬운 문제는 더 빨리 뽑기 위해 우선순위 큐를 이용하여 값이 작은 것을 우선으로 뽑아준다.

코드

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int cnt[32003];
vector<int> v[32003];
priority_queue<int, vector<int>, greater<int>> q; // 작은 것부터 뽑음

int main() {
    int N, M; scanf("%d %d", &N, &M);
    while (M--) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b);
        cnt[b]++;
    }
    for (int i = 1; i <= N; i++) {
        if (!cnt[i]) q.push(i);
    }
    while (!q.empty()) {
        int cur = q.top();
        q.pop();
        printf("%d ", cur);
        for (auto nxt : v[cur]) {
            if (--cnt[nxt] == 0) q.push(nxt);
        }
    }
}