[Python] 백준 2623 음악프로그램

2623번: 음악프로그램

위상정렬 : 위상정렬의 핵심은 그래프와 진입차수 같다. 여기 입력이 꼬여버리면 복잡해진다. 마지막에 주의할 점은 가수 순서를 못만들때를 고려해 주어야 한다. result의 길이로 판별을 했다.

 

전체코드

import sys
import collections

input = sys.stdin.readline

N, M = map(int, input().split())
inDegree = [0 for _ in range(N + 1)]
graph = collections.defaultdict(list)
for _ in range(M):
    singer = list(map(int, input().split()))[1:]
    for i in range(1, len(singer)):
        graph[singer[i - 1]].append(singer[i])
        inDegree[singer[i]] += 1

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

result = []
while queue:
    node = queue.popleft()
    result.append(node)
    for i in graph[node]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            queue.append(i)
if len(result) == N:
    print(*result)
else:
    print(0)