(라이님 블로그 대회 알고리즘 따라잡기 20) 위상 정렬(Topological Sort)

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220800013823&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

위상 정렬(Topological Sort) (수정: 2017-06-22)

 

최소 스패닝 트리와 뭔가뭔가 비슷한 느낌의 알고리즘

 

그래프의 정점을 정렬하는 방법으로 선수과목이 있는 문제들에서 사용 가능한 알고리즘이다. 

 

라이님의 백준 2623번 문제를 vector를 사용해서 약간만 바꿔보았다. 

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

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int N, M; scanf("%d %d", &N, &M);

	vector<vector<int>> adj(N);
	vector<int> indegree(N, 0);

	for (int i = 0; i < M; i++) {
		int K, prev, curr;
		scanf("%d", &K);
		if (K > 0) {
			scanf("%d", &prev);
			for (int j = 1; j < K; j++) {
				scanf("%d", &curr);
				indegree[curr - 1]++;
				adj[prev - 1].push_back(curr - 1);
				prev = curr;
			}
		}
	}
	
	queue<int> Q;
	vector<int> result;

	for (int i = 0; i < N; i++) {
		if (indegree[i] == 0) Q.push(i);
	}

	for (int i = 0; i < N; i++) {
		if (Q.empty()) {
			puts("0");
			return 0;
		}

		int curr = Q.front();
		Q.pop();
		result[i] = curr + 1;

		for (int next : adj[curr])
			if (--indegree[next] == 0) Q.push(next);
	}

	for (int i = 0; i < N; i++)
		printf("%d\n", result[i]);
}

 

이건 라이님의 백준 1516번 풀이에서 array 생성 부분만 수정한 코드다.

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

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

int main() {
	int N;
	scanf("%d", &N);

	vector<int> time(N), result(N, 0), indegree(N, 0);
	vector<vector<int>> adj(N);
	queue<int> Q;

	for (int i = 0; i < N; i++) {
		scanf("%d", &time[i]);
		while (1) {
			int pre;
			scanf("%d", &pre);
			if (pre == -1) break;
			indegree[i]++;
			adj[pre - 1].push_back(i);
		}
		if (indegree[i] == 0) {
			result[i] = time[i];
			Q.push(i);
		}
	}

	for (int i = 0; i < N; i++) {
		int curr = Q.front();
		Q.pop();
		for (int next : adj[curr]){
			result[next] = max(result[next], result[curr] + time[next]);
			if (--indegree[next] == 0) Q.push(next);
		}
	}

	for (int i = 0; i < N; i++)
		printf("%d\n", result[i]);
}