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

문제 링크 : www.acmicpc.net/problem/1766

 

 

위상정렬 문제이다.

 

위상정렬 알고리즘  :  wlshddlek.tistory.com/39?category=887828

 

 

<전체적인 알고리즘>

위상정렬을 이용해야 한다. 위상정렬을 이용할 때 일반 큐가 아니라 우선순위 큐를 사용하면 

실시간으로 탐색할 수 있는 것 중에 작은거 부터 탐색할 수 있다.

 

 

<전체 코드>

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m;
vector<int> a[32002];
int indegree[32002];

void topology()  //우선순위큐를 이용한 위상 정렬
{
	priority_queue<int> pq;  //실시간으로 선택할 수 있는 것 중 가장 작은거 선택 위함
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)pq.push(-i);  //우선순위 큐는 내림차순 정렬이라서 -붙임
	}

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

		cout << node << " ";

		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i];
			indegree[next]--;
			if (indegree[next] == 0)pq.push(-next);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int n1, n2;
		cin >> n1 >> n2;
		a[n1].push_back(n2);
		indegree[n2]++;
	}

	topology();

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.