위상정렬

학과 커리큘럼을 보면 우선적으로 특정 과목을 들어야 다른 과목을 수강 할 수 있는 과목들이 있다.
예를 들면, 알고리즘 1 -> 알고리즘 2 -> 고급 알고리즘과 같이 말이다.
위상정렬은 이렇게 우선순위를 정해주어야 할 때 쓸 수 있는 알고리즘이다.

소프트웨어 공학의 팬-인 팬-아웃과 비슷한 개념인 것 같다.

문제풀이 전략
1. indegree가 0 인 노드를 큐에 넣는다.
2. 그래프를 하나씩 순회하면서 비교할 노드를 pop 하고 연결된 노드의 간선의 수를 하나씩 줄인다 .
3. 간선의 수가 0이면 노드를 다시 큐에 삽입한다.

from collections import deque
v, e = map(int, input().split())
indegree = [0] * (v+1)
graph = [[] for _ in range(v+1)]

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

def topology_sort():
	q = deque()
	result = []
	for i in range(1, v+1):
		if indegree[i] == 0:
			q.append(i)
	while q:
		now = q.popleft()
		result.append(now)
		for i in graph[now]:
			indegree[i] -= 1
			if indegree[i] ==0 :
				q.append(i)
	for i in result:
		print(i, end = ' ')

topology_sort()