b_줄세우기_2252

문제

큰애 작은애 순으로 주어진다
이 조건을 만족하는 줄을 출력한다

답

부모가 없는 노드를 먼저 선택해야함

• 내가 틀린점
  • 부모입장에서의 그래프와 자식입장에서의 그래프 2개를 만들어서 사용했다
  • 이럴 필요없고 진입차수만확인하고 그래프 정보를 담고있는 객체를 하나만두면된다.

import sys
from collections import deque

N,M = map(int,sys.stdin.readline().strip().split())
graph = {} # key 부모 values자식
incnt = [0] * (N+1)
for _ in range(M):
    a,b=map(int,sys.stdin.readline().strip().split())
    graph.setdefault(a, set()).add(b)
    incnt[b] += 1

que = deque()
for i in range(1,N+1):
    if incnt[i] == 0:
        que.append(i)
output = ""

while que:
    # print(que)
    tmp = que.popleft()
    output += f"{tmp} "
    sons = graph.setdefault(tmp,set())
    for s in sons:
        incnt[s] -= 1
        if incnt[s] == 0:
            que.append(s)

print(output)