[백준 ] 1766 : 문제집

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())
tr = [[] for _ in range(N + 1)]
inDg = [0 for _ in range(N + 1)]

q = []
# 문제 순서
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    tr[a].append(b)
    inDg[b] += 1

# 진입차수가 0이면 큐에 넣기
for i in range(1, N + 1):
    if inDg[i] == 0:
        heapq.heappush(q, i)

# 위상정렬
rs = []
while q:
    a = heapq.heappop(q)  # 최소힙 사용
    rs.append(a)
    for i in tr[a]:
        inDg[i] -= 1
        if inDg[i] == 0:
            heapq.heappush(q, i)

print(*rs)

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

이 문제는 위상정렬을 사용해야만 하기에 위상정렬을 참고하여 풀이했다

참고 : https://blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)