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

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

14567번: 선수과목 (Prerequisite)

[필자 사고]

이 문제는 위상정렬 알고리즘을 사용하여 해결할 수 있는 문제이다.

 

또한 이 문제만의 특이한 점은 필자가 사용한 Level변수를 사용하여 위상정렬에 맞게 레벨처리를 완료해야 되는 문제다.

 

[소스 코드]

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

int N, M;

vector<vector<int>> Arr;
vector<int> dist;
vector<int> Record;
void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	Record.resize(N + 1);
	dist.resize(N + 1, 0);
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		Arr[s].push_back(e);
		dist[e]++;
	}
}

void Topological_Sort() {
	queue<int> myQueue;
	for (int i = 1; i <= N; i++) {
		if (dist[i] == 0) {
			myQueue.push(i);
		}
	}
	int Level = 1;
	int LevelSize = myQueue.size();
	int LevelCount = 0;
	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();
		Record[nowIdx] = Level;
		LevelCount++;
		for (int nextIdx : Arr[nowIdx]) {
			dist[nextIdx]--;
			if (dist[nextIdx] == 0) {
				myQueue.push(nextIdx);
			}
		}
		if (LevelCount == LevelSize) {
			LevelCount = 0;
			LevelSize = myQueue.size();
			Level++;
		}
	}
}

int main(void) {
	Input();
	Topological_Sort();
	for (int i = 1; i <= N; i++) {
		cout << Record[i] << " ";
	}
}