[Alg] 위상 정렬 (Topology Sort)

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례로 수행해야 할 때 사용할 수 있는 알고리즘으로,
방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.
위상 정렬 알고리즘에서는 진입 차수라는 개념이 필요한데, 진입 차수란 특정한 노드로 들어오는 간선의 개수를 의미한다.

위상 정렬 알고리즘

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

# 위상 정렬 알고리즘

import sys
class queue:
    def __init__(self):
        self.queue = []
        self.size = 0
    def enqueue(self, x):
        self.queue.insert(0, x)
        self.size += 1
    def dequeue(self):
        if self.isEmpty():
            return None
        self.size -= 1
        return self.queue.pop()
    def isEmpty(self):
        return self.size == 0
    def dequeueAll(self):
        self.queue = []
        self.size = 0

v, e = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(v+1)]
indegree = [0 for _ in range(v+1)]  # 진입 차수
for _ in range(e):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    indegree[y] += 1

def topologySort():
    q = queue()
    result = []
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.enqueue(i)
    while not(q.isEmpty()):
        x = q.dequeue()
        result.append(x)
        for i in graph[x]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.enqueue(i)
    for i in result:
        print(i, end=" ")
topologySort()