백준 1766번 문제집 C++ (골드2)

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

 

어떤 문제를 풀기전에 풀어야 하는 문제가 있기 때문에 이에 적합한 위상정렬을 사용해서 문제를 해결하였다.

그리고 번호가 낮은 문제부터 풀어야 하기 때문에 위상정렬에서 사용하는 큐를 우선순위 큐로 바꾸고 낮은 번호부터 뽑히도록 하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<vector<int>> graph;
vector<int> inDegree;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    graph = vector<vector<int>>(n + 1, vector<int>());
    inDegree = vector<int>(n + 1, 0);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        inDegree[b]++;
        graph[a].push_back(b);
    }
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++)
    {
        if (inDegree[i] == 0) pq.push(i);
    }
    vector<int> ans;
    while (!pq.empty())
    {
        int curr = pq.top();
        ans.push_back(curr);
        pq.pop();
        for (int next : graph[curr])
        {
            if (inDegree[next] == 1) pq.push(next);
            else inDegree[next]--;
        }
    }
    for (auto a : ans)
    {
        cout << a << " ";
    }
}