문제집

• 여러개의 가능한 위상 정렬 순서 중에서도, 특정 순서 기준으로 가장 빠른 순서에 해당되는 것을 찾는 문제 유형이다.
• 위상 정렬 (Topological Sorting)에서 설명했듯이, DFS를 이용해서 위상정렬을 할때에는 쉽지 않지만, Kahn's algorithm을 사용할 때에는 큐를 우선순위큐로 바꿔서 써주기만 하면 쉽게 해결할수 있다.
• 여기에서는 graphlib.TopologicalSorter을 사용해서 구현했는데, 이 경우에는 static_order() 함수를 쓰지 말고, 루프 안에서 get_ready()와 done()함수를 호출하면서 위상정렬을 하면 구현이 가능하다. 위상 정렬 문재 유형 참고.
• 시간복잡도는 V개의 원소를 우선순위큐에 추가/삭제 해야 하므로 O(VlogV + E)가 된다.

"""Solution code for "BOJ 1766. 문제집".

- Problem link: https://www.acmicpc.net/problem/1766
- Solution link: http://www.teferi.net/ps/problems/boj/1766

Tags: [TopologicalSort]
"""

import graphlib
import heapq
import sys


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    ts = graphlib.TopologicalSorter()
    for i in range(1, N + 1):
        ts.add(i)
    for _ in range(M):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        ts.add(B, A)

    answer = []
    heap = []
    ts.prepare()
    while ts:
        for problem in ts.get_ready():
            heapq.heappush(heap, problem)
        problem_to_solve = heapq.heappop(heap)
        answer.append(problem_to_solve)
        ts.done(problem_to_solve)

    print(*answer)


if __name__ == '__main__':
    main()