acmicpc_1005(ACM Craft)

위상정렬 알고리즘을 통하여 해결하였다. 위상 정렬 알고리즘(Topology Sort)은 어떤 일을 하는 순서를 찾는 알고리즘이다. 방향 그래프에서 각 정점의 작업(?)수행 순서에 따라서 정렬은 한다고 볼 수 있다.

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

int n, k;
int time[1001];
int dp[100001];
int degree[100001];
vector<int> v[100001];

int a, b, c;

void clear() {
	for (int i = 1; i <= n; ++i) {
		dp[i] = 0;
		time[i] = 0;
		degree[i] = 0;
		fill(v[i].begin(), v[i].end(), 0);
	}
}
void bfs() {
	queue<int> q;

	for (int i = 1; i <= n; ++i) {
		if (degree[i] == 0) {
			q.push(i);
			dp[i] = time[i];
		}

	}
	while (!q.empty()) {

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

		for (int i = 0; i < v[edge].size(); ++i) {
			int nedge = v[edge][i];
			dp[nedge] = max(dp[nedge], dp[edge] + time[nedge]);

			if (--degree[nedge] == 0) {
				q.push(nedge);
			}

		}
	}
}
int main() {
	int t;
	cin >> t;
	for (int x = 0; x < t; ++x) {

		cin >> n >> k;
		for (int i = 1; i <= n; ++i) {
			cin >> time[i];
		}
		for (int i = 1; i <= k; ++i) {
			cin >> a >> b;
			v[a].push_back(b);
			degree[b]++;
		}

		bfs();
		cin >> c;
		cout << dp[c]<<'\n';
		clear();
	}


}

개인적으로 bfs와 비슷하다고 생각하고, topology이름이 조금 길기도 하고.. 혼자 작성하는 코드이기때문에 bfs이름으로 작성하였다. 변수 a와 b에서 a가 우선으로 작업하고 그 후 b를 작업한다.(a->b)

degree는 진입차수의 개수를 말해주고 진입차수가 0이되면 그 때의 정점이 작업을 시작한다.