January 27, 2023

2252번: 줄 세우기

문제 요약

• N명의 학생들을 키 순서대로 줄을 세우는 방법 출력
• M개의 학생들 간 키 관계가 주어짐
• 1 ≤ N ≤ 32,000, 1 ≤ M ≤ 100,000

풀이

from collections import deque
from sys import stdin

input = stdin.readline

N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
in_degree_list = [0] * (N + 1)
q = deque()

for _ in range(M):
    A, B = map(int, input().split())
    edges[A].append(B)
    in_degree_list[B] += 1

for i in range(N):
    if (in_degree_list[i + 1] == 0):
        q.append(i + 1)

for _ in range(N):
    if (not q):
        # 위상 정렬 불가능
        break
    start = q.popleft()
    print(start, end=' ')

    for end in edges[start]:
        in_degree_list[end] -= 1
        if (in_degree_list[end] == 0):
            q.append(end)

• 위상정렬 이용

시간 복잡도

• O(V + E)