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

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

2623번: 음악프로그램

 

문제 해결

• 위상정렬의 대표적인 문제이다.
• 위상정렬이란 사이클이 없는 방향 그래프에 노드 순서를 찾는 알고리즘이다.
• 앞에 필요한 순서가 없는 것을 indegree=0으로 두고 앞에 노드가 이어져있으면 +1 씩 해서
• 나중에 시작 가능한 지점부터 돌 때 노드가 연결되서 지나갈 때마다 indegree를 1씩 줄여 indegree=0이 되는 순서대로 출력시키는 문제이다.
• 만약 사이클이 생겨 한 문자가 중복되서 돌게 되면 모순이 있는 것이므로 0을 출력하면 된다.

 

CODE

import sys
from collections import deque

n, m = map(int, input().split())
indegree = [0]*(n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, *order = map(int, input().split())
    for i in range(len(order)-1):
        indegree[order[i+1]] += 1
        graph[order[i]].append(order[i+1])
que = deque()
for i in range(1,n+1):
    if indegree[i] ==0:
        que.append(i)
answer = []
while que:
    now = que.popleft()
    answer.append(now)
    for next in graph[now]:
        indegree[next] -= 1
        if indegree[next]==0:
            que.append(next)
if len(answer) != n:
    print(0)
else:
    for i in range(n):
        print(answer[i])