우선순위큐 공부

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

using namespace std;
//각 정점간위 순서를 나타낼 정점들의 배열
vector <vector <int>> v;
//우선순위 큐
priority_queue< int, vector<int>, greater<int> > pq;
const int Max = 32e3;

int main(void) {

	int N, M;
	int from, to;
	int degree[Max+1] = { 0 };

	cin >> N >> M;
	v.resize(N + 1);

	for (int i = 0; i < M; i++) {
		cin >> from >> to;
		v[from].push_back(to);
		degree[to]++;
	}

	//degree가 0인 것들을, 순서대로 먼저 우선순위 큐에 삽입처리
	for (int i = 1; i <= N; i++) {
		if (!degree[i])
			pq.push(i);
	}

	int now;
	while (!pq.empty()) {
		now = pq.top();
		pq.pop();
		printf("%d ", now);
		//총 v[now]와 관련된 정점(now가 선행하는)의 개수만큼 for문 진행
		//이것과 관련된 것들의 degree를 1씩 없애고, 이를 우선순위 큐에 삽입
		for (auto next : v[now])
			if (--degree[next] == 0)
				pq.push(next);
	}
	
	return 0;
}

priority_queue<int, vector<int>, greater<int>> v 등으로 우선순위 큐의 대체가 가능

각 정점과 수반되는 정점을 만들 때마다, vector<vector<int>>로 정의된 2중벡터에서 vector<from>의 요소에 to를 하나 추가한다. 이를 반복

 

이후엔, degree를 토대로, 0이 아닌 것들은 수반되는 것 없이 처리되는 것들이므로, 죄다 삽입한다

이후엔, 이것들을 처리하면서, 이것과 수반되는 것이 있다면(이는, v[now]의 요소가 0인지 아닌지의 요소로 판별 가능하다) 만약 0이라면 이는 now를 선행으로 하는 정점이면서 동시에 이후에 선행해야 할 요소가 없다는 뜻이기도 하다. 따라서 즉시 큐에 삽입한다. 이때, pq에 삽입하면 알아서 우선순위를 토대로 정렬이 된다. c++의 위대함!

 

따라서, 이를 큐가 완전히 빌 때까지 반복하면 된다.