[BOJ/백준] 2623 음악 프로그램

import sys
from collections import deque

input = sys.stdin.readline


N,M = map(int,input().split())
graph = [set() for _ in range(N+1)]
degree = [0 for _ in range(N+1)]
for _ in range(M):
    pdN,*arr = list(map(int,input().split()))

    for i in range(pdN-1):
        x,y = arr[i],arr[i+1]
        if y not in graph[x]:
            graph[x].add(y)
            degree[y] += 1

stack = deque()
cnt = 0
result = []
flag = True

for i in range(1,N+1):
    if degree[i]==0:
        stack.append(i)
while cnt<N:
    if not stack:
        flag = False
        break
    node = stack.popleft()
    result.append(str(node))
    for next_node in graph[node]:
        degree[next_node] -= 1

        if degree[next_node] == 0:
            stack.append(next_node)
    cnt += 1

if flag:
    print('\n'.join(result))
else:
    print(0)

이 문제와 같은 경우 평범한 위상정렬이다.

 

여러명의 PD를 통해 앞에서부터, 하나씩 그래프에 SET으로 넣어주었다.

 

그리고 degree가 0인것들은 최초의 stack에 넣어주고 난뒤에 위상정렬을 구해주면서,

 

사이클이 발생할 시, 음악프로그램을 구할 수 없는 것이므로, 그때 flag로 분기 처리를 해주었다.

 

그리고 stack에 나온순서대로 result에 넣어주고 출력을 해주었다.