2252번 줄 세우기

 위상 정렬 기본 문제.

 

 각 정점에 해당하는 inDegree를 계산한 후 0(우선순위가 높은)부터 시작하여 갯수를 줄여나가면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001
 
using namespace std;
 
int N,M;
int inDegree[MAX];
vector<int> vec[MAX];
 
void topologySort(){
 
    queue<int> q;
    
    for(int i=1;i<=N;i++){
        if(inDegree[i]==0) q.push(i);
    }
    
    while(!q.empty()){
        int x=q.front();
        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=1;i<=M;i++){
        int a,b;
        cin >> a >> b;
        vec[a].push_back(b);
        inDegree[b]++;
    }
    
    topologySort();
    
    return 0;
}