2623: 음악 프로그램

문제 링크

2623: 음악 프로그램

구현 방식

• 순서가 정해진 단방향 그래프에서 노드들의 순서를 정하는 문제이므로 위상 정렬로 풀어주었다
• 모든 노드를 방문하지 못했을 경우(len(result) != N인 경우), cycle이 발생한 경우이므로 0을 출력해줘야 한다

코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())
graph = [[] for n in range(N+1)]; root = []
indegree = [0] * (N+1)
for m in range(M):
    tmp = list(map(int, sys.stdin.readline().strip().split())); tmp = tmp[1:]
    for i in range(len(tmp)-1): graph[tmp[i]].append(tmp[i+1]); indegree[tmp[i+1]] += 1
    root.append(tmp[0])

def topology_sort():
    queue = deque()

    for n in range(1, N+1):
        if indegree[n] == 0: queue.append(n)
    
    while queue:
        cur = queue.popleft()
        result.append(cur)

        for nex in graph[cur]:
            indegree[nex] -= 1
            if indegree[nex] == 0: queue.append(nex)

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