1766번: 문제집 (힙, 위상정렬) - Fastcampus

www.acmicpc.net/problem/1766

1766번: 문제집

import sys
import heapq


# 문제 푸는 순서 결정하기 => 위상정렬 (진입차수가 0인 정점을 큐에 추가)
def search(N, indgree):
    res = []
    qu = []

    for i in range(1, N+1):
        if indgree[i] == 0:
            heapq.heappush(qu, i)  

    while qu:
        node = heapq.heappop(qu)
        res.append(node)

        for e in graph[node]:
            indgree[e] -= 1
            if indgree[e] == 0:
                heapq.heappush(qu, e)  # 힙을 이용하므로 쉬운 문제 순서로 추출된다

    return res


N, M = map(int, input().split())

graph = [[] for _ in range(N + 1)]
indgree = [0] * (N + 1)

for _ in range(M):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    indgree[y] += 1

ans = search(N, indgree)
[print(x, end=" ") for x in ans]