[백준/BOJ] 백준 1766번 : 문제집

www.acmicpc.net/problem/1766

1766번: 문제집

 

위상정렬을 이용하였는데, 큐는 우선순위 큐를 써서 우선순위 큐에 풀 수 있는 문제를 저장할 때 (-문제 번호)를 저장하여 가능하면 쉬운 문제부터 풀도록 하였다.

 

코드

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

int n, m;
vector<int> adj[32001];
vector<int> indegree(32001, 0);
priority_queue<int> pq;

//위상 정렬 알고리즘을 이용
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;

		cin >> a >> b;

		adj[a].push_back(b);
		indegree[b]++;
	}

	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)
			pq.push(-i); //가능하면 쉬운 문제 부터 풀어야 하므로 -i를 우선순위 큐에 저장
	}

	vector<int> result;
	while (!pq.empty())
	{
		int here = -pq.top();
		pq.pop();

		result.push_back(here);

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			indegree[there]--;

			if (indegree[there] == 0)
				pq.push(-there);
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";

	return 0;
}