백준 1766 : 문제집

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

1766번: 문제집

 

어떤 문제를 해결하기 전 우선적으로 풀어야할 문제가 주어지는 위상정렬 문제다.

다만 이 문제에서는 동일한 우선순위를 가진 문제라고 할지라도 문제 번호가 더 작은 쪽이 더 높은 우선순위를 가진다는 조건이 하나 더 추가되는데, 이는 우선순위큐를 사용함으로써 구현할 수 있다.

 

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

using namespace std;

int n;
vector<int> edge[32'001];
int pre_cnt[32'001];
vector<int> ans;

void bfs() {
	int cur, next;
	priority_queue<int> pq;

	for (int i = 1; i <= n; i++) {
		if (!pre_cnt[i]) pq.push(-i);
	}

	//현재 풀 수 있는 문제들 중
    //문제 번호가 가장 작은 것부터 해결
	while (!pq.empty()) {
		cur = -pq.top();
		pq.pop();

		cout << cur << ' ';

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

			if (!pre_cnt[next]) pq.push(-next);
		}
	}
}

void solution() {
	int m, before, later;
	cin >> n >> m;
	while (m--) {
		cin >> before >> later;
		edge[before].push_back(later);
		++pre_cnt[later];
	}

	bfs();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 3968 kb

시간: 40 ms