백준 1766 문제집 (C++)

1766번: 문제집

위상 정렬을 이용한 문제이다. 난이도가 낮은 순서대로 접근을 해야하기 때문에 우선순위 큐를 사용하여 위상 정렬을 구현해주었다. 위상 정렬에 대해 잘 아는지 확인하는 문제였다. 어렵지 않게 풀 수 있었다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
int inDegree[32001];
vector<int> v[32001];
vector<int> result;

void findResult() {
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) pq.push(i);
	}

	while (!pq.empty()) {
		int cur = pq.top();

		result.push_back(cur);
		pq.pop();

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

			inDegree[next]--;

			if (inDegree[next] == 0) pq.push(next);
		}
	}
}

void solution() {
	findResult();

	for (auto elem : result) {
		cout << elem << " ";
	}
}

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

	cin >> N >> M;

	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		inDegree[b]++;
	}

	solution();
	
	return 0;
}