[알고리즘] 백준 1766 문제집 / 위상정렬, python

 

import heapq

n, m = map(int, input().split(' '))
num_list = [ [] for _ in range(n+1) ]
indegree = [ 0 for _ in range(n+1) ]
heap = []
result = []

for _ in range(m):
    a, b = map(int, input().split(' '))
    num_list[a].append(b)
    indegree[b] += 1

for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

while heap:
    temp = heapq.heappop(heap)
    result.append(temp)
    for i in num_list[temp]:
        indegree[i] -= 1
        if indegree[i] == 0:
            heapq.heappush(heap, i)

for i in result:
    print(i, end=' ')

위상정렬 알고리즘 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘
시간복잡도 = O( V + E )

1. 진입 차수가 0인 정점을 큐에 삽입한다
2. 큐에서 원소를 꺼내 해당 원소와 간선을 제거한다
3. 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입한다
4. 큐가 빌 때까지 2~3을 반복