파이썬 백준 1766 문제집

import sys
input = sys.stdin.readline
from heapq import heappush, heappop
 
Vn, En = map(int, input().split())
V = {}
parent = [0 for i in range(Vn + 1)]
for i in range(1, Vn + 1) : 
    V[i] = []
for i in range(En) : 
    v1, v2 = map(int, input().split())
    V[v1].append(v2)
    parent[v2] = parent[v2] + 1
 
heap = []
for i in range(1, Vn + 1) : 
    if parent[i] == 0 : 
        heappush(heap, i)
 
while heap : 
    i = heappop(heap)
    print(i, end = ' ')
    for j in V[i] : 
        parent[j] = parent[j] - 1
        if parent[j] == 0 : 
            heappush(heap, j)
 

degree를 세어 0인 점부터 위상정렬하는 정석적인 문제이다.

단 쉬운 문제부터 푼다(= 동위상에서 사전순을 우선해야 한다)는 조건이 있으므로, deque 대신 heap을 이용한다.