백준 2623 음악프로그램 python

2623 음악프로그램
참고: 위상 정렬 강의(동빈나)

위상 정렬
사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열
진입차수 : 특정한 노드로 들어오는 간선의 개수
진출차수: 특정한 노드로 나가는 간선의 개수
위상 정렬 알고리즘의 동작 과정 (큐사용)
진입차수가  0 인 모든 노드를 큐에 넣는 다
큐가 빌때까지 아래를 반복
1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는 다
-> 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다

시간 복잡도 O(V+E)

import sys; input = lambda : sys.stdin.readline().rstrip()
from collections import deque


N, M = map(int, input().split()) # N 가수의 수 M 보조 pd의 수
graph = [[] for _ in range(N+1)] # 연결 리스트
indegree = [0] * (N+1) # 진입 차수
for _ in range(M):
    singer = list(map(int, input().split()))
    for i in range(1, len(singer)-1):
        graph[singer[i]].append(singer[i+1])
        indegree[singer[i+1]] += 1

# 위상 정렬 구현
result = []
q = deque()
for i in range(1, N+1):
    if not indegree[i]:
        q.append(i)
while q:
    now = q.popleft()
    result.append(now)
    for j in graph[now]:
        indegree[j] -= 1
        if not indegree[j]:
            q.append(j)

if len(result) != N:
    print(0)
else:
    for r in result:
        print(r)