파이썬 백준 2623 음악프로그램

import sys
input = sys.stdin.readline
from collections import deque
 
n, m = map(int, input().split())
V = {}
parent = [0 for i in range(n + 1)]
for i in range(1, n + 1) : 
    V[i] = []
for i in range(m) : 
    l = list(map(int, input().split()))
    for i in range(1, l[0]) : 
        V[l[i]].append(l[i+1])
        parent[l[i+1]] = parent[l[i+1]] + 1
 
que = deque()
for i in range(1, n + 1) : 
    if parent[i] == 0 : 
        que.append(i)
ans = []
while que : 
    i = que.popleft()
    ans.append(i)
    for j in V[i] : 
        parent[j] = parent[j] - 1
        if parent[j] == 0 : 
            que.append(j)
 
if len(ans) == n : 
    for i in ans : 
        print(i)
else : 
    print(0)

IDEA

인풋받은대로 위상정렬하여 출력하면 되는 정석적인 문제이지만, 불가능한 경우 0을 출력해야 한다.

위상정렬 BFS는 정석적으로 구현하되, 답을 ans로 저장한다.

ans의 길이가 n과 같다면 모든 점이 제대로 된 순서를 가진 것이니 출력한다.

n이 아니라면 어딘가에 사이클이 있어 잘못된 결과가 나온 것이므로 0을 출력한다.