[백준] 14567번 선수과목 파이썬 코드

코드

# 선수과목에는 사이클이 생길 수 없다. 따라서 유향 비순환 그래프이다.
# 몇 학기 째에 들을 수 있는지 확인해야하므로 위상정렬 이용

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

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
indegree = [0]*(n+1) # 전입차수
visited = [0]*(n+1) # 학기 기록용 방문리스트

for _ in range(m):
  x,y = map(int, input().split())
  graph[x].append(y)
  indegree[y]+=1

def topol_sort():
  queue = deque()
  for i in range(1, n+1): # 전입차수가 0인 값을 찾아 덱에 추가
    if indegree[i] == 0:
      queue.append(i)
      visited[i] = 1 # 1학기에 들을 수 있음을 의미
  while queue:
    popnum = queue.popleft()
    for j in graph[popnum]:
      indegree[j] -= 1
      visited[j] = visited[popnum]+1 # 다음 과목을 이수할 수 있음을 의미
      if indegree[j] == 0: queue.append(j)
topol_sort()
print(*visited[1:])