문제
풀이
위상 정렬에 대한 문제이다. 최소힙을 통해 상황마다 낮은 값을 출력하게 하면 정답 도출이 가능하다. 파이썬 내에서 heapq는 최소힙이다.
heap = []으로 리스트를 선언해 준 뒤, heapq.heappush(heap, i)로 heap에 값을 넣고, heapq.heappop(heap)으로 최소값을 pop하고 return하도록 한다.
c++의 prioirty_queue는 최대힙으로, 마이너스를 통해 관리하여 최소힙으로 구현한다.
소스 코드
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
import sys
from math import *
import collections as cl
import heapq
N, M = map(int, sys.stdin.readline().split())
tree = [[] for _ in range(N+1)]
degree = [0 for _ in range(N+1)]
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
tree[a].append(b)
degree[b] += 1
heap = []
result_list = []
for i in range(1, N+1):
if degree[i] == 0:
heapq.heappush(heap, i)
while(heap):
current = heapq.heappop(heap)
result_list.append(current)
for i in tree[current]:
degree[i] -= 1
if(degree[i] == 0):
heapq.heappush(heap, i)
print(*result_list)
