백준 1766번 문제집 (C++)

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

1766번: 문제집

위상 정렬문제이다.

줄세우기 문제와 유사하지만 중요한 건 이번에는 이왕이면 더 작은 수 부터 해야하기 때문에 bfs 방식만을 사용해서 우선순위큐를 만들어줘야한다.

 

정답 코드

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

int N, M;
vector<int> graph[32001];
bool check[32001] = { false, };
int degree[32001];

priority_queue<int, vector<int>, greater<int>> pq;

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

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		degree[i] = 0;
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		graph[a].push_back(b);
		degree[b]++;
	}

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

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

		cout << node << " ";

		for (int i = 0; i < graph[node].size(); i++) {
			int now_node = graph[node][i];

			if (check[now_node]) continue;
			
			degree[now_node]--;
			
			if (degree[now_node] == 0) {
				pq.push(now_node);
				check[now_node] = true;
			}
		}
	}
}