[백준] 음악프로그램

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

위상정렬을 활용하는 문제입니다. 모든 출연자에 대해 순서를 정해주어야하는데 각 작가별로 입력받은 순서에 따라 그래프를 구축한 다음 위상정렬을 통해 순서를 정해주면 됩니다. 순서를 정해줄 수 없는 경우는 위상정렬 시작을 위해 큐에 넣는 과정에서 큐에 하나의 노드도 넣을 수 없는 경우, 위상 정렬중에 in_node의 값이 음수가 되는 경우 그리고 위상정렬이 끝났는데 n개의 노드에 대해 위상정렬이 되지 않은 경우 모두 그래프 내에 싸이클이 존재하여 순서를 정할 수 없는 경우가 됩니다.

 

import sys
from collections import defaultdict, deque

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

graph =defaultdict(list)
in_node = [0] * (n + 1)

for _ in range(m):
    order = list(map(int, input().split()))

    cnt = order[0]
    # 다음 순서에 해당하는 출연자를 가르키게 한다.
    for i in range(1, cnt):
        graph[order[i]].append(order[i + 1])

        in_node[order[i + 1]] += 1


q = deque()
for i in range(1, n + 1):
    if in_node[i] == 0:
        q.append(i)
# 시작할 수 있는 정점이 없는 경우
if not q:
    print(0)
    sys.exit(0)

ans = []
while q:
    cur = q.popleft()
    ans.append(cur)

    for next_node in graph[cur]:
        in_node[next_node] -= 1

        if in_node[next_node] == 0:
            q.append(next_node)
        # 만약 싸이클에 의해 in_node가 0보다 작아지면 순서를 정할 수 없다.
        elif in_node[next_node] < 0:
            print(0)
            sys.exit(0)

if len(ans) == n:
    for a in ans:
        print(a)
# 모든 출연자에 대해 위상 정렬이 불가능한 경우
else:
    print(0)