[위상 정렬] 백준 2252번: 줄 세우기 / 골드 2

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

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

import sys
import collections
input = sys.stdin.readline

n, k = map(int, input().split())
deg = [0 for _ in range(n)]
graph = collections.defaultdict(list)

for _ in range(k):
    a, b = map(int, input().split())
    graph[a].append(b)
    deg[b-1] += 1

q = collections.deque()
for i in range(n):
    if deg[i] == 0:
        q.append(i+1)

while q:
    cur = q.popleft()
    print(cur, end=' ')

    for next in graph[cur]:
        deg[next-1] -= 1
        if deg[next-1] == 0:
            q.append(next)

위상 정렬의 기본 유형이다. 골드 2인 건 살짝 의문이다.