BOJ 2623 - 음악프로그램 - Python

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

전체 가수의 순서를 정하는 것이다.
위상정렬을 통해서 해결할 수 있다.
가장 기본적인 위상정렬을 하고,
마지막에 모든 가수가 정상적으로 result에 들어갔는지를 확인 해주면 된다.

from collections import deque

N, M = map(int, input().split())
indegree = [0] * (N + 1)
arr = [[] for _ in range(N + 1)]

for i in range(M):
    temp = list(map(int, input().split()))
    for j in range(1, temp[0]):
        arr[temp[j]].append(temp[j + 1])
        indegree[temp[j + 1]] += 1

result = []
queue = deque()

for i in range(1, N + 1):
    if indegree[i] == 0:
        queue.append(i)

while len(queue):
    temp = queue.popleft()
    result.append(temp)  # 뺀 값은 indegree가 0이었다는 소리이므로 result에 들어간다.

    for second in arr[temp]:
        indegree[second] -= 1
        if indegree[second] == 0:  # indegree가 0이 됐을 때 queue에 넣는다.
            queue.append(second)

if len(result) == N:  # 모든 가수가 정상적으로 result에 들어갔다면 만들 수 있는 것
    for element in result:
        print(element)
else:  # 아니라면 실패
    print(0)