[위상 정렬] BOJ 1766 문제집 (C++)

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

1766번: 문제집

 

문제 해결 알고리즘

 

전형적인 위상정렬 알고리즘 문제였으나 가능하면 쉬운 문제부터 푼다는 조건이 들어가있는 문제이다.

 

이 문제는 위상정렬할 때 쓰이는 큐를 우선순위 큐로 오름차순 정렬해주면 풀리는 문제였다.

 

아래는 링크는 위상정렬 알고리즘에 대해 자세히 설명되어있다.

 

https://kimmessi.tistory.com/207

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N, M;

int indegree[32002];
vector<int> graph[32002];

void topologySort(){

    vector<int> result;
    priority_queue<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++){

            indegree[graph[now][i]]--;

            if(indegree[graph[now][i]] == 0){
                pq.push(-graph[now][i]);
            }
        }
    }

    for(int i=0;i<result.size();i++) {
        cout << result[i] << ' ';
    }
}

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);
    cin >> N >> M;

    for(int i=0;i<M;i++){
        int A, B; cin >> A >> B;

        graph[A].push_back(B);

        indegree[B]++;
    }

    topologySort();
}