[위상 정렬] BOJ 14567 선수과목 (Prerequisite)

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

14567번: 선수과목 (Prerequisite)

 

문제 해결 알고리즘

 

전형적인 위상 정렬 문제이다.

 

아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다.

 

https://kimmessi.tistory.com/207

[알고리즘] 위상 정렬 (Topology Sort) - BFS

 

소스 코드

 

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

int v, e, cnt = 1;

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

void topologySort(){

    vector<int> result(1001);
    queue<int> q;


    for(int i=1;i<=v;i++){
        if(indegree[i] == 0){
            q.push(i); result[i] = cnt;
        }
    }

    cnt++;

    while(!q.empty()){

        int now = q.front();
        q.pop();


        for(int i=0;i<graph[now].size();i++){
            indegree[graph[now][i]] -= 1;

            if(indegree[graph[now][i]] == 0){
                q.push(graph[now][i]);
                result[graph[now][i]] = result[now]+1;
            }
        } 
    }

    for(int i=1;i<=v;i++) cout << result[i] << ' ';
}

int main(){
    
    cin >> v >> e;

    for(int i=0;i<e;i++){
        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);

        indegree[b]+=1;
    }

    topologySort();
}