백준 2252 줄 세우기

과정

• 위상정렬
  https://velog.io/@minyule/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC
• 반드시 a 뒤쪽에 b가 위치해야 한다.

• a, b 의 관계를 그래프로 입력받고, 배열에 진입차수를 추가해나간다.
• 큐에 진입차수가 0인 값을 모두 추가한다.
• 큐에서 pop 하고, 배열에서 진입차수를 1 뺀다.
  • 진입차수가 0이면, 큐에 추가한다.
  • 큐의 길이가 0이 되면 중단한다.
• 큐에 push된 순서대로 출력한다.

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())

lst = [0] * (N+1)

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    lst[b] += 1
    
def topologicalSort():
    queue = deque()
    stack = []

    for i in range(1, N+1):
        if lst[i] == 0:
            queue.append(i)
            stack.append(i)
            
    while queue:
        a = queue.popleft()
        for b in graph[a]:
            lst[b] -= 1
            if lst[b] == 0:
                queue.append(b)
                stack.append(b)
                
    return stack


print(*topologicalSort())