[BOJ/백준] 2252 줄 세우기

import sys
 
input = sys.stdin.readline
 
from collections import deque
 
N, M = map(int,input().split())
 
graph = [{} for _ in range(N+1)]
parents_cnt = [0]*(N+1)
result = []
visited = [True]*(N+1)
for _ in range(M):
    A,B = map(int,input().split())
    graph[A][B] = 1
    parents_cnt[B] += 1
 
que = deque()
for i in range(1,N+1):
    if not parents_cnt[i]:
        que.append(i)
for i in range(N):
    x = que.popleft()
    result.append(x)
 
    for next_node in graph[x]:
        parents_cnt[next_node] -= 1
        if parents_cnt[next_node] == 0:
            que.append(next_node)
print(*result)
 
 

m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

 

위상정렬에 관련된 처음 보는 문제였고, 순서가 정해진 작업을 차례대로 작업할 순서를 정할때 쓰는 알고리즘이라는 것을 알았다.

 

이 알고리즘에 대해 더 공부하고, 기본 틀을 완성시켜놔야할것 같다.