[백준] 1766: 문제집

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

1766번: 문제집

 

위상 정렬 문제에서 좀 더 정렬 조건을 추가한 문제이다.

위상 정렬 + 가능한 쉬운(작은 숫자의) 문제부터 정렬 

=> 오름차순 우선순위 큐를 사용한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b;
vector<int> graph[100004];
int indegree[32004];
vector<int> result;

void topologySort(){
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=1;i<=n;i++){
        if (indegree[i]==0) pq.push(i);
    }
    while(!pq.empty()){
        int now = pq.top();
        pq.pop();
        result.push_back(now);
        for(int i=0;i<graph[now].size();i++){
            int node = graph[now][i];
            indegree[node]-=1;
            if(indegree[node]==0) pq.push(node);
        }

    }
}

int main(){
    // 1. 입력받기
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> a >> b;
        graph[a].push_back(b);
        indegree[b] += 1;
    }
    // 2. 위상정렬
    topologySort();
    // 3. 결과 출력
    for(int r:result) cout << r << " ";
}