[백준 C++] 1766 문제집 - 위상정렬

1766번: 문제집

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

list<int> Neighbor[32001];
int Entry[32001];

priority_queue<int, vector<int>, greater<int>> PQ;
list<int> Sorted;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int S, E;
		cin >> S >> E;
		Neighbor[S].emplace_back(E);
		++Entry[E];
	}

	for (int i = 1; i <= N; ++i)
	{
		if (Entry[i] == 0)
		{
			PQ.emplace(i);
		}
	}

	while (!PQ.empty())
	{
		int Current = PQ.top();
		PQ.pop();

		Sorted.emplace_back(Current);

		for (const int& N : Neighbor[Current])
		{
			--Entry[N];
			if (Entry[N] == 0)
			{
				PQ.emplace(N);
			}
		}
	}

	for (const int& Num : Sorted)
	{
		cout << Num << ' ';
	}
}

---

 

우선순위 큐를 이용해서 푸는 위상정렬 문제입니다.

일반적인 위상정렬 문제 풀이대로 풀되,

문제에서 제시한 3번 조건에 따라서 우선순위 큐를 이용해서 적은 숫자 먼저 정답 배열에 배치하도록 해야 합니다.