선수과목 (Prerequisite) (feat. 백준, 14567번)

선수과목 (Prerequisite)
https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
vector<int> arr[1001];
int check[1001]{0};
int ans[1001]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    cin >> N >> M;
    for(register int m = 0, a, b; m < M; ++m){
        cin >> a >> b, arr[a].push_back(b), ++check[b];
    }
    queue<int> q;
    for(register int n = 1; n <= N; ++n){
        if(!check[n])
            q.push(n);
        ans[n] = 1;
    }
    while(!q.empty()){
        auto pos = q.front(); q.pop();
        for(auto& v : arr[pos])
            if(--check[v] == 0)
                q.push(v), ans[v] = max(ans[v], ans[pos] + 1);
    }
    for(register int n = 1; n <= N; ++n)
        cout << ans[n] << ' ';
	return 0;
}
// *&)*@*

 

반응형

위상정렬을 이용하는 문제입니다.

1번 과목은 몇학기에, 2번 과목은 몇학기에, N번 과목은 몇학기에 이수 가능한지를 출력하는 문제입니다.