1766. 문제집

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

1766번: 문제집

• 특징
  • 우선순위큐를 사용한 위상정렬
• 구현방법
  • 큐를 사용하는 기본적인 위상정렬 알고리즘에서 큐를 우선순위큐(오름차순)로 바꾸면된다. 
  • 큐에 문제가 들어있을 때, 쉬운 순서부터 pop해야함으로 우선순위큐를 사용한다. 
• 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<int> adj[32002];
int deg[32002];
priority_queue<int, vector<int>, greater<int>> pq; 
vector<int> result;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        deg[v]++;
    }

    for(int i = 1; i <= n; i++)
    {
        if(deg[i] == 0) pq.push(i);
    }

    while(!pq.empty())
    {
        int cur = pq.top(); pq.pop();
        result.push_back(cur);
        for(auto nxt: adj[cur])
        {
            deg[nxt]--;
            if(deg[nxt] == 0) pq.push(nxt);
        }
    }
    
    for(auto x: result) cout << x << ' ';
}