[위상 정렬/파이썬] 백준 2623번 : 음악프로그램 / 골드2

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

2623번: 음악프로그램

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한

www.acmicpc.net

import collections

n, m = map(int, input().split())

graph = collections.defaultdict(list)
indegree = [0 for _ in range(n)]

for _ in range(m):
    lst = list(map(int, input().split()))
    for i in range(2, lst[0]+1):
        a = lst[i-1]
        b = lst[i]
        graph[a].append(b)
        indegree[b-1] += 1

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

order = []
while nums:
    cur = nums.popleft()

    order.append(cur)
    for next in graph[cur]:
        indegree[next-1] -= 1
        if indegree[next-1] == 0:
            nums.append(next)

if n != len(order):
    print(0)
    quit()
else:
    for i in range(len(order)):
        print(order[i])

골드2이긴하지만 전형적인 위상정렬 문제다.

위상 정렬이 불가능한 경우는 order에 모든 원소가 들어가 있는지 여부로 판단이 가능하다.

불가능한 경우 => 사이클이 발생하여 nums에 추가되지 못하기 때문이다.