# 테페리넷

### 사이트 도구

ps:problems:boj:2623

# 음악프로그램

ps
링크acmicpc.net/…
출처BOJ
문제 번호2623
문제명음악프로그램
레벨골드 2
분류

위상정렬

시간복잡도O(v+e)
인풋사이즈v<=1000, e<=100000
사용한 언어Python
제출기록29340KB / 76ms
최고기록60ms
해결날짜2020/11/25

## 코드

"""Solution code for "BOJ 2623. 음악프로그램".

"""

from typing import AbstractSet, List, Sequence

def topological_sort(graph: Sequence[AbstractSet[int]]) -> List[int]:
"""Returns a list of nodes in topologically sorted order."""
indegrees = [0] * len(graph)
for successors in graph:
for v in successors:
indegrees[v] += 1

stack = [u for u, indegree in enumerate(indegrees) if indegree == 0]
result = []
while stack:
u = stack.pop()
result.append(u)
for v in graph[u]:
indegrees[v] -= 1
if indegrees[v] == 0:
stack.append(v)

if len(result) != len(graph):
raise ValueError('found a cycle')
return result

def main():
N, M = [int(x) for x in input().split()]
graph = [set() for _ in range(N)]
for _ in range(M):
n, *singers = [int(x) for x in input().split()]
for i in range(n - 1):
graph[singers[i] - 1].add(singers[i + 1] - 1)

try:
result = topological_sort(graph)
print(*[x + 1 for x in result], sep='\n')
except ValueError:
print(0)

if __name__ == '__main__':
main()

## 토론

댓글을 입력하세요:
B L O O H

ps/problems/boj/2623.txt · 마지막으로 수정됨: 2020/11/25 17:09 저자 teferi