[백준] 1766번 위상정렬

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int N,M,a,b;
int isDone[32001] = {0,}; //모두 0으로 초기화
vector<int> seq[32001];
priority_queue<int, vector<int>, greater<>> pq;

int main(){
    cin>>N>>M;
    for(int i=0; i<M; i++){
        cin>>a>>b;
        isDone[b]++;
        seq[a].push_back(b);
    }
    for(int i=1; i<=N; i++){
        if(isDone[i]==0){
            pq.push(i);
        }
    }
    while(!pq.empty()){
        int problem = pq.top();
        pq.pop();
        cout<<problem<<" ";
        for(int i=0; i<seq[problem].size(); i++){
            int next = seq[problem][i];
            isDone[next]--;
            if(isDone[next]==0){
                pq.push(next);
            }
        }
    }
    cout<<"\n";
    return 0;
}

<참고>

https://jungahshin.tistory.com/218

<설명>

위상정렬: 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

isDone[i]: i 전에 먼저 풀어야 하는 문제 개수

seq[i]: 노드 i에서 갈 수 있는 다음 문제들

pq: 진입 차수가 0인 문제들을 담아두는 우선순위 큐, greater<int>이므로 작은 수가 먼저 나옴

problem: 번호가 가장 작은 문제 선택

next: 다음 문제

while(!pq.empty()){             // 큐에 아직 처리할 문제가 있으면 계속
    int problem = pq.top();     // 가장 먼저 풀 수 있는 문제 번호 가져오기
    pq.pop();                   // 큐에서 제거
    cout << problem << " ";     // 출력 (= 문제 푼다고 생각)

    // 이제 이 문제를 풀었으니, 이 문제 덕분에 풀 수 있는 문제들을 업데이트!
    for(int i=0; i<seq[problem].size(); i++){
        int next = seq[problem][i];  // 다음 문제
        isDone[next]--;              // 이 문제 덕분에 next의 진입 차수 감소
        if(isDone[next]==0){         // 다 해결되면 큐에 추가
            pq.push(next);
        }
    }
}

if(isDone[next] == 0) {

    pq.push(next);

}: 어떤 문제를 풀게된 후에 풀 수 있게 된 다음 문제들을 큐에 넣는다.