설명

위상정렬이란 사이클이 없는 방향그래프가 주어졌을 때 모든노드를 방향성을 거스르지 않으며
순서대로 나열하는 것이다.

방법을 단순화 해본다면 이렇게 해볼 수 있다!!!

1.진입차수가 0인 노드를 큐에 넣는다.
2.큐가 빌때까지 다음 두 과정을 반복한다.
a.큐에 있는 노드를 꺼내 연결되어있는 간선을 그래프에서 제거한다.
b.방금 과정에서 진입차수가 0이된 노드를 큐에 넣는다.

코드로 구현해본다면

코드

#위상정렬 코드 파이썬
from collections import deque
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
graph = [[]for _ in range(V+1)]
indegree = [0] * (V+1)

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

def topology_sort():
  result = []
  q = deque()
  for i in range(1, V+1):
    if indegree[i] == 0:
      q.append(i)
  while q:
    now = q.popleft()
    result.append(now)

    #꺼낸 노드와 연결돼있는 노드들의 진입차수 -1해주기
    for j in graph[now]:
      indegree[j] -= 1
      if(indegree[j] == 0):
        q.append(j)

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

topology_sort()

시간 복잡도

위 알고리즘은 모든 노드와 간선을 확인하므로

시간 복잡도는 O(V+E)가 된다.