1766번: 문제집

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


$O(m+n\lg n)$

위상정렬을 할 때, indegree가 0이면서 가장 작은 번호의 문제를 먼저 푼다.

#include<cstdio>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
const int MXN = 32e3;
int n, m, x, y, ind[MXN + 1];
vector<int> adj[MXN + 1];
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
    for (scanf("%d%d", &n, &m); m--;) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        ind[y]++;
    }
    for (int i = 1; i <= n; i++) if (!ind[i]) pq.push(i);
    while (!pq.empty()) {
        int h = pq.top();
        pq.pop();
        printf("%d ", h);
        for (auto it : adj[h]) if (!--ind[it]) pq.push(it);
    }
    return 0;
}