[백준] 14567 선수과목 (Prerequisite) c++

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

14567번: 선수과목 (Prerequisite)

 

풀이과정

dp와 위상정렬을 같이 쓰는 문제다.  
위상정렬 함수를 보면 진입차수가 0일 경우(1,4,6번 노드)에 큐에 푸시를 하며 정답 배열에 1을 넣어준다.  
그리고 큐가 비어있지 않을 때까지 연결되어있는 노드를 돌며 dp를 해주며 최종적으로 max인 값(res)를 출력해준다.

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

int N, M, A, B;
int indegree[1001]; // 진입차수
int res[1001]; // dp

queue <int> q;
vector <int> v[1001];

void topologySort() {
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			res[i] = 1;
		}
	}

	while (!q.empty()) {
		int now = q.front();
		q.pop();

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

			res[next] = max(res[next], res[now] + 1);
			if (indegree[next] == 0) {
				q.push(next);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> A >> B;
		v[A].push_back(B);
		indegree[B]++;
	}

	topologySort();
	for (int i = 1; i <= N; i++) {
		cout << res[i] << " ";
	}
}