백준 1766 C++

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

using namespace std;

// 작은 수가 먼저 오도록 우선순위 큐에 greater<int>를 사용
priority_queue<int, vector<int>, greater<int>> pq;

// 문제 풀이의 최종 순서
vector<int> answer;

int main(void){
	int N, M;
    cin >> N >> M;

    /** 위상 및 그래프 표현 **/
    
    // 각 노드의 진입 차수를 저장
    // 1부터 N까지의 인덱스를 가지는 vector를 모두 0값으로 초기화
    vector<int> topology(N + 1, 0);
    // 인접 리스트: 특정 노드와 연결된 다른 노드를 저장
    vector<vector<int>> graph(N + 1);

    // 문제 간의 관계 입력
    for(int i = 0; i < M; i++){
        // 나중에 풀어야 하는 문제의 진입 차수를 높임
        // 먼저 풀 문제 a, 그 다음에 풀어야 하는 문제 b
        int a, b;
        cin >> a >> b;
        
        topology[b]++;  // 문제 b의 진입 차수 증가
        graph[a].push_back(b);  // 그래프에 의존 관계 추가
    }

    // 진입 차수가 0인 문제를 우선순위 큐에 추가
    for(int i = 1; i <= N; i++){
        if(topology[i] == 0){
            pq.push(i);
        }
    }

    // 주어진 조건에 따라 문제를 풀기
    for(int i = 1; i <= N; i++){
        int tmp = pq.top();  // 진입 차수가 가장 작은 문제 가져오기
        answer.push_back(tmp);  // 문제를 풀이 순서에 추가
        pq.pop();  // 우선순위 큐에서 해당 문제 제거

        // 진입 차수를 업데이트하고 새로운 문제를 우선순위 큐에 추가
        for(int j = 0; j < graph[tmp].size(); j++){
            int node = graph[tmp][j];

            if(--topology[node] == 0){
                pq.push(node);
            }
        }
    }

    for(int i = 0; i < N; i++){
        cout << answer[i] << " ";
    }

    return 0;
}