import sys
input = sys.stdin.readline
from collections import deque
N,M = map(int,input().split())
indegree = [0]*(N+1)
child = [[] for i in range(N+1)]
for i in range(M):
x1,x2 = map(int,input().split())
child[x1].append(x2)
indegree[x2] += 1
dq = deque()
for i in range(1,N+1):
if indegree[i] == 0:
dq.append(i)
seq = []
while dq:
x = dq.popleft()
for i in child[x]:
indegree[i] -= 1
if indegree[i] == 0:
dq.append(i)
seq.append(x)
print(" ".join(map(str,seq)))
도저히 풀이방법이 안떠올라서 며칠을 묵혀놨던 문제.
위상정렬 알고리즘으로 푸는 문제라고 해서 결국 위상정렬에 대해서 읽어보고 구현할 수 있었다.
위상정렬 알고리즘의 가장 핵심은 진입차수이다. 진입차수(indegree)가 0인 것들만 골라서 줄을 세우면 된다.
진입차수라는 개념에 대해서 배울 수 있었던 좋은 문제였다
오늘의 교훈) 위상정렬 문제들을 풀어보자