[백준/Python] 2252번 줄 세우기 - (위상 정렬)

문제

https://www.acmicpc.net/submit/2252/86061561

 

소스코드

import sys 
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

indegree = [0] * n
grape = {}
for i in range(m):
    a, b = map(int, input().split())
    if a - 1 not in grape:
        grape[a - 1] = []
    grape[a - 1].append(b - 1)
    indegree[b - 1] += 1

queue = deque()
for i in range(n):
    if indegree[i] == 0:
        queue.append(i)
answer = []
while queue:
    temp = queue.popleft()
    answer.append(temp + 1)
    if temp in grape:
        for go in grape[temp]:
            indegree[go] -= 1
            if indegree[go] == 0:
                queue.append(go)
print(*answer)

 

위상정렬 풀이입니다. 

 

예로 1 3 이 주어지면 학생 1이 학생 3보다 앞에 서야하기때문에 학생 3의 진입 간선으로 학생 1을 설정하여 위상정렬을 진행하면 됩니다.