[백준/BOJ] 1766 문제집

문제 : 1766 문제집

1766번: 문제집

각 문제를 푸는 시간과 선행 문제가 주어졌을 때,

문제집에서 문제를 푸는 순서를 출력하는 문제이다.

위상 정렬을 사용하지만 가능하면 쉬운 문제부터 풀어야 하므로

그냥 큐가 아니라 우선순위 큐로 위상 정렬을 한 후 출력하면 된다. 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, chk[32005];
vector<ll> arr[32005];
void TopologySort(){
    ll ret=0;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (int i=1;i<=N;i++){
        if (chk[i]==0)
            pq.push(i);
    }
    for (int i=1;i<=N;i++){
        ll x=pq.top();
        pq.pop();
        cout << x << " ";
        for (int j=0;j<arr[x].size();j++){
            ll dx=arr[x][j];
            if (--chk[dx]==0)
                pq.push(dx);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0;i<M;i++){
        ll a, b;
        cin >> a >> b;
        arr[a].push_back(b);
        chk[b]++;
    }
    TopologySort();
    return 0;
}