사용자 도구

사이트 도구


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. 음악프로그램".

- Problem link: https://www.acmicpc.net/problem/2623
- Solution link: http://www.teferi.net/ps/problems/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