위상 정렬 예제

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

from collections import deque

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

adj = [[] for _ in range(N)]
need_to_learn = [0]*N

for _ in range(M):
    a,b = list(map(int, input().split()))
    
    adj[a-1].append(b-1)
    need_to_learn[b-1] += 1
    
# 위상 정렬
queue = deque([]) # 처리 가능 목록
for i in range(N):
    if need_to_learn[i] == 0:
        queue.append(i) # 리스트에 쌓아두고 하나씩 처리 위함
        
learn = [] # 실제 처리 완료 목록
while len(queue) != 0:
    u = queue.popleft()
    learn.append(u)
    
    for v in adj[u]:
        need_to_learn[v] -= 1
        if need_to_learn[v] == 0:
            queue.append(v)
            
for i in range(N):
    print(learn[i]+1, end=" ")

 

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

 

from queue import PriorityQueue

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

adj = [[] for _ in range(N)] # 방향 그래프 인접 리스트 초기화
need_to_learn = [0]*N

for _ in range(M):
    a, b = list(map(int, input().split()))
    
    adj[a-1].append(b-1)
    need_to_learn[b-1] += 1

# 위상 정렬 - 번호 작은 것 우선 위해 PriorityQueue 사용
pq = PriorityQueue()

for i in range(N):
    if need_to_learn[i] == 0:
        pq.put(i) # 바로 풀 수 있는 문제 후보들
        
learn = [] # 수강 순서 저장
while pq.qsize() != 0:
    u = pq.get() # 번호 가장 작은 것이 나옴
    learn.append(u)
    
    for v in adj[u]:
        need_to_learn[v] -= 1
        if need_to_learn[v] == 0:
            pq.put(v) # 해당 선수과목 이수로 인해 선수과목 0이 된 경우 바로 풀 수 있는 문제 후보에 추가
            
for i in range(N):
    print(learn[i]+1, end=" ") #위에서 index 1씩 빼서 수행했으므로 다시 원복하여 출력