1. 문제 설명

음악 프로그램

2. 문제 분석

위상 정렬 조건 중 정렬이 불가능한 경우는 in-degree를 하나씩 제거해갈 때, 다음에 queue에 삽입되는 노드가 존재하지 않는 상태다. 즉 while문이 조기 종료되기 때문에, 정렬된 노드의 수가 정렬하려는 기존의 수보다 작다.

3. 나의 풀이

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
in_degree = [0 for _ in range(n+1)]
for _ in range(m):
    singers = list(map(int, sys.stdin.readline().rstrip().split()))
    if singers[0] > 0:
        for i in range(1, singers[0]+1):
            for j in range(i+1, singers[0]+1):
                nodes[singers[i]].append(singers[j])
                in_degree[singers[j]] += 1
                # tail -> head 연결

queue = deque()
result = []
for i in range(1, n+1):
    if in_degree[i] == 0:
        queue.append(i)

while queue:
    cur_node = queue.popleft()
    result.append(cur_node)

    for next_node in nodes[cur_node]:
        in_degree[next_node] -= 1
        if in_degree[next_node] == 0:
            queue.append(next_node)

if len(result) != n: print(0)
# 불가능하다는 뜻은 queue 반복문 중 in-degree가 0이 되는 케이스가 없다는 뜻이므로 조기 종료된다는 뜻.
else: print(*result, sep='\n')