[백준] 1766 - 문제집

[문제]

---

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

[풀이]

---

위상정렬이긴한데 또 오름차순으로 정렬하는 문제이다.
기존 위상정렬은 deque 자료구조를 썼으나 큐 안에 있는 원소 중 가장 작은 것부터 뽑기 위해 그냥 heapq를 썼다.

[코드]

---

import sys, heapq
r=sys.stdin.readline

n,m=map(int,r().split())
l=[[] for _ in range(n+1)]
degree = [0] * (n+1)
for _ in range(m):
    a,b = map(int,r().split())
    l[a].append(b)
    degree[b] += 1

q = []
for i in range(1, n+1):
    if degree[i] > 0: continue
    heapq.heappush(q, i)
arr = [0]*n
for i in range(n):
    pop = heapq.heappop(q)
    arr[i] = pop
    for e in l[pop]:
        degree[e]-=1  
        if degree[e] == 0:
            heapq.heappush(q, e)

print(*arr)