[Python] 위상정렬 - 14567. 선수과목 (골5)

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

14567번: 선수과목 (Prerequisite)

 

>>문제 포인트

: 위상정렬 문제인데 위상정렬로 안품

:  A<B라는 조건을 활용

: 연결정보가 주어지면 무조건 한번 더 들어야 함

: 앞에서부터 최소 학기를 완성하고 하나씩 result 배열 완성해주기

 

v,e = map(int, input().split())

result = [1]*(v+1)

edge=[]

for _ in range(e):

  a,b = map(int, input().split())

  edge.append((a,b))

#각 과목 번호로 오름차순 하여 선수과목에 따른 최소이수 학기를 하나씩 완성해감

edge.sort(key=lambda x: (x[1], x[0]))

for i in edge:

  result[i[1]]= max(result[i[1]], result[i[0]]+1)

print(*result[1:])