1766번 문제집

 위상 정렬 기본 문제.

 

 우선 순위 큐를 사용하여 위상 정렬을 구현하면 된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001
 
using namespace std;
 
int N,M;
int inDegree[MAX];
vector<int> vec[MAX];
 
void topologySort(){
    
    priority_queue<int,vector<int>,greater<int>> q;
    
    for(int i=1;i<=N;i++){
        if(inDegree[i]==0) q.push(i);
    }
    
    while(!q.empty()){
        int x=q.top();
        q.pop();
        
        cout << x << " ";
        
        for(int i=0;i<vec[x].size();i++){
            inDegree[vec[x][i]]--;
            if(inDegree[vec[x][i]]==0){
                q.push(vec[x][i]);
            }
        }
    }
}
 
int main(){
    cin >> N >> M;
    
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        vec[a].push_back(b);
        inDegree[b]++;
    }
    
    topologySort();
}