[백준/BOJ] 1766번 문제집 (C++)

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

1766번: 문제집

 

위상 정렬을 이용하는 문제, 그러나 '가능하면 쉬운 문제부터 풀어야 한다.' 라는 조건을 만족하기 위해서 큐 대신 우선순위 큐를 사용한다.

 

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

int N, M;
int degree[32001];
vector<int> graph[32001];

void topol() {
	priority_queue<int, vector<int>, greater<int> > pq;
	
	for(int i = 1; i <= N; i++) {
		if(degree[i] == 0) pq.push(i);
	}
	
	while(!pq.empty()) {
		int now = pq.top();
		pq.pop();
		
		cout << now << " ";
		
		for(int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			degree[next]--;
			if(degree[next] == 0) pq.push(next);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N >> M;
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		degree[b]++;
	}
	
	topol();
}