백준 14567번 : 선수과목 (Prerequisite)
2021. 10. 5. 22:12ㆍ문제풀기/백준
https://www.acmicpc.net/problem/14567
14567번: 선수과목 (Prerequisite)
3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.
www.acmicpc.net
아이디어
전형적인 위상정렬 문제이다.
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().rstrip().split())
routes = [0] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
a,b = map(int,input().rstrip().split())
graph[a].append(b)
routes[b] += 1
queue = deque([])
visitied = [0] * (n+1)
for i in range(1,n+1):
if routes[i] == 0:
visitied[i] = 1
queue.append(i)
while queue:
now = queue.popleft()
for i in graph[now]:
visitied[i] = visitied[now] + 1
routes[i] -= 1
if routes[i] == 0:
queue.append(i)
for i in range(1,n+1):
print(visitied[i], end =' ')
'문제풀기 > 백준' 카테고리의 다른 글
14179 : 빗물 (0) | 2022.01.04 |
---|---|
백준 22860번 : 폴더 정리(small) (0) | 2021.10.06 |
백준 1548번 : 부분 삼각 수열 (0) | 2021.10.05 |
백준 7576번 : 토마토 (0) | 2021.10.05 |
백준 20436 : ZOAC 3 (0) | 2021.10.05 |