테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 음악프로그램 ======
 
===== 풀이 =====
  * 전형적인 [[ps:위상 정렬]] 문제. 딱히 추가할 설명이 없다.

===== 코드 =====
<dkpr py>
"""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()
</dkpr>