• 선행이 필요하기 때문에 topological sort
  • 숫자가 낮은 문제를 먼저 풀어야 하기 때문에 priority queue 사용
  • indegree[to]가 0일 때만 queue에 push하면 되는데, to를 만날 때마다 queue에 push하고 꺼낼 때 해당 indegree가 0인지 여부를 확인하는 과정을 넣는 바람에 메모리 초과가 발생했다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58



#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <queue>

using namespace std;

#define MAX_N 32010

int N, M;
vector<int> edge[MAX_N];
int indegree[MAX_N];
vector<int> res;

void solution() {
	for (int i = 1; i <= N; i++)
		sort(edge[i].begin(), edge[i].end());

	priority_queue<int> pq;
	for (int from = 1; from <= N; from++) {
		if (indegree[from] == 0) {
			pq.push(-from);
		}
	}

	while (!pq.empty()) {
		int from = -pq.top();
		pq.pop();
		
		res.push_back(from);
		
		for (int i = 0; i < edge[from].size(); i++) {
			int to = edge[from][i];
			indegree[to]--;
			if (indegree[to] == 0)
				pq.push(-to);
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		int from, to;
		scanf("%d%d", &from, &to);

		edge[from].push_back(to);
		indegree[to]++;
	}

	solution();

	for (int i = 0; i < res.size(); i++)
		printf("%d ", res[i]);
}