줄세우기 (위상정렬)

하나의 개념을 이해하는데서 그치는게 아니라 이를 활용하려면 여러 군데에 응용해서 활용해보는 것이 가장 효과적인 것 같습니다.

 

위상정렬 또한 개념을 이해했지만 구현하려고 하니 막히거나 다른 부분과 헷갈리는 부분이 있었고 복습 겸 간단히 풀어보았습니다.

 

 

from collections import deque

n , m = map(int,input().split())

q = deque()

indegree = [0]*(n+1)

board = [[] for _ in range(n+1)]

# print(board)

 

for i in range(m):

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

    indegree[b]+=1

    board[a].append(b)

 

for i in range(1,n+1):

    if indegree[i]==0:

        q.append(i)

 

answer = []

while q:

    front = q.popleft()

    answer.append(front)

    for i in range(len(board[front])):

        next = board[front][i]

        indegree[next]-=1

        if indegree[next]==0:

            q.append(next)

 

for a in answer:

    print(a, end=" ")