위상 정렬(Topology Sort)

 위상 정렬 알고리즘은 방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법을 의미합니다. 기존의 서로소 집합 알고리즘이나, 이를 기반으로 한 크루스칼 알고리즘은 무향 그래프에 대해서 동작했던 것을 생각하면 차이가 있습니다. 예를 들어 '선수과목을 고려한 학습 순서 설정 문제' 등에서 대표적으로 사용될 수 있습니다.

---

1. 각 노드의 진입차수(indegree)를 저장합니다.

2. 진입차수가 0인 노드부터 시작하여 연결된 노드에 대해 진입차수를 1씩 뺍니다.

3. 다른 노드도 진입차수가 0이 될 경우 2의 동작을 반복합니다.

---

 큐를 사용하여 구현할 경우 위상정렬의 시간복잡도는 O(V+E)입니다. 전체 소스코드는 다음과 같습니다.

input1 = '''7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4'''

from collections import deque

v, e = list(map(int, input1.split('\n')[0].split()))
indegree = [0] * (v + 1)
array = [list(map(int, row.split())) for row in input1.split('\n')[1:]]

graph = [[] for _ in range(v + 1)]
for a, b in array:
    graph[a].append(b)
    indegree[b] += 1
    
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)
        
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
                
    for i in result:
        print(i, end=' ')

topology_sort()