문제

https://www.acmicpc.net/problem/1766

Input)
4 2
4 2
3 1
Output)
3 1 4 2

Point

풀 수 있는 문제 중 가장 쉬운(숫자 작은) 문제를 골라서 푼다.

부모 문제가 여러개 일 수 있다.

• 부모가 하나 풀렸다고 해서 그 자식 문제들을 probs에 다 넣어버리면, 그 중 다른 부모 문제가 있는 문제에서 문제 발생
• probs에 새롭게 풀 수 있는 문제를 추가하는 기준을, "남은 부모 문제가 없는 문제"로 한다.
  ("방금 푼 문제의 자식문제들"이 아닌)

변수

• probs : 현재 풀 수 있는 문제들
• sons : 나 이후로 나올 수 있는 문제들
• pars : 나보다 먼저 나와야(풀려야) 할 문제들

전체코드

n, m = [int(x) for x in input().split()]

sons = [set() for _ in range(n+1)]
pars = [set() for _ in range(n+1)]
probs = set(list(range(1,n+1)))

for i in range(m):
  a, b = [int(x) for x in input().split()]
  sons[a].add(b)
  pars[b].add(a)
  probs.discard(b) # b는 풀 수 있는 문제들에서 제외된다.

asw = []
soled = [0]*(n+1)
while len(asw)<n:
  sol = min(probs) # 풀 수 있는 문제 들 중 가장 작은 것 풀기
  soled[sol] = 1 # sol 문제 풀었다고 처리
  asw.append(sol)
  probs.remove(sol)
  for a in sons[sol]: # a: sol 이후로 나올 수 있는 문제
    pars[a].remove(sol) # a 이전에 나와야 할 문제 하나(sol) 삭제
    if len(pars[a]) == 0 and soled[a] == 0: # 이제 a이전에 나와야 할 문제 없다면 probs에 추가
      probs.add(a)

print(*asw)