[1766] 문제집

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> v[32001];
int indegree[32001];
priority_queue<int, vector<int>, greater<int>> pq;
void bfs()
{

    while (!pq.empty())
    {
        int next = pq.top();
        cout << next << " ";
        pq.pop();
        for (int y : v[next])
        {
            int nextnode = y;
            indegree[nextnode] -= 1;
            if (indegree[nextnode] == 0)
            {

                pq.push(nextnode);
            }
        }
    }
}
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int src, dest;
        cin >> src >> dest;
        v[src].push_back(dest);
        indegree[dest]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            pq.push(i);
            //  cout << i << "\n";
        }
    }
    bfs();
    return 0;
}

bfs 를 활용한 위상 정렬 알고리즘이다.
여기서 주의 해야할 점은 최소 힙을 썼다는 것인데, 문제의 조건에 의하면 가능하면 쉬운 문제 부터 풀어야 한다라는 것이 있으므로, 가장 작은 수부터 큐에서 pop을 하여야 한다.