[#알고리즘/위상 정렬/[백준]2252번: 줄 세우기(python)]

Question

https://www.acmicpc.net/problem/2252

Code

from collections import deque
import sys

input =  sys.stdin.readline

n, m = map(int, input().split())
# 진입차수 
indegree = [0] * (n + 1)
# 학생들의 키 관계 정보를 담을 list
graph = [[] for _ in range(n + 1)]

# 학생들의 키 관계 입력받기
for _ in range(m) :
    a, b = map(int, input().split())
    # 학생 a가 학생 b 앞에 서야함.
    graph[a].append(b)
    # 학생 b의 진입차수를 1 증가
    indegree[b] += 1
    
# 위상정렬
def topology_sort() :
    result = []  # 위상정렬 수행 결과를 담을 list
    q = deque()
    
    # 처음 시작 시 진입차수가 0인 학생을 큐에 삽입
    for i in range(1, n + 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()