[위상 정렬] 백준 1766번: 문제집 / 골드 2

https://www.acmicpc.net/problem/1766

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

import heapq
import collections
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
deg = [0 for _ in range(n+1)]
graph = collections.defaultdict(list)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    deg[b] += 1

q = []
for i in range(1, n+1):
    if deg[i] == 0:
        heapq.heappush(q, i)

result = []
while q:
    now = heapq.heappop(q)
    result.append(now)
    for i in graph[now]:
        deg[i] -= 1
        if deg[i] == 0:
            heapq.heappush(q, i)

print(*result)

난이도는 골드2로 되어있으나

위상 정렬 유형의 기본 문제라고 할 수 있다.

최대한 작은 문제를 풀려고 하기 때문에 최소힙을 사용하는 것 정도가 추가된 느낌이다.