import sys
input = sys.stdin.readline
from heapq import heappop,heappush
N,M = map(int,input().split())
indegree = [0]*(N+1)
graph = {i:[] for i in range(1,N+1)}
for i in range(M):
x,y = map(int,input().split())
indegree[y] += 1
graph[x].append(y)
hq = []
seq = []
for i in range(1,N+1):
if indegree[i] == 0:
heappush(hq,i)
while hq:
now = heappop(hq)
seq.append(now)
for next in graph[now]:
indegree[next] -= 1
if indegree[next] == 0:
heappush(hq,next)
print(" ".join(map(str,seq)))
위상정렬을 알면 아주 쉽게 풀 수 있는 문제.
위상정렬 알고리즘을 이용했던 줄세우기 문제와 코드가 거의 똑같지만 딱 하나, dq를 heapq로 바꿔주었다는 것만 다르다.
가능한 번호가 작은것부터 풀어야 하기 때문에 최소힙을 이용해준다.
간단한 문제였지만 이 문제의 풀이가 다른 문제에 활용하기 좋겠다는 생각도 했다. 이 문제에서는 난이도를 번호순이라고 해서 쉬웠지만, 이후에 어떤 순서로 배열하는 문제가 나왔을 때 이 문제에서의 개념을 활용할 수 있을 것이다.
오늘의 교훈) 위상정렬 + heapq를 잘 활용하자