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

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

1766번: 문제집

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m, a, b, indegree[MAX];
	vector<int> v[MAX];
	priority_queue<int, vector<int>, greater<int>> q;
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++){
		cin >> a >> b;
		v[a].push_back(b);
		indegree[b]++;
	}
	
	for(int i = 1; i <= n; i++){
		if(indegree[i] == 0) q.push(i);
	}
	
	for(int i = 1; i <= n; i++){
		int x = q.top();
		q.pop();
		
		cout << x << " ";
		
		for(int j = 0; j < v[x].size(); j++){
			int y = v[x][j];
			if(--indegree[y] == 0) q.push(y);
		}
	}
	
	return 0;
}

 

 

1766번과 비슷한 위상정렬 문제이다.

'가능하면 쉬운 문제부터 풀어야 한다'는 조건이 있기 때문에 우선순위 큐를 사용한다.