608 위상정렬

방향 그래프의 노드를 방향성에 거스르지 않고 순서대로 나열하는 것

예시 : Like 커리큘럼

1. 진입차수가 0인 노드를 큐에 넣는다
2. 큐가 빌때까지
   • 큐에서 원소를 커내 해당노드에서 출발하는 간선을 제거한다.
   • 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

from collections import deque

# <span id="v-는-노드개수"></span>v 는 노드개수
# <span id="graphnodeappend연결된노드"></span>graph[node].append(연결된노드)
inde = [0] * (v+1) # 노드에 대한 진입차수

def topology_sort():
    result = []
    q = deque()
    # 진입차수가 0인거 큐에 삽입
    for i in range(1,n+1):
        if inde[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        #now 에서 출발한 간선에 대해서 진입차수 제거
        for i in graph[now]:
            inde[i] -= 1
            if inde[i] == 0:
                q.append(i)