[python]伯俊2623-音楽番組の解答


Overview


BOJ 2623番音楽番組Python解答
分類:トポロジソート

質問ページ


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

プールコード

from sys import stdin
from collections import defaultdict, deque
from typing import List


graph = defaultdict(list)
indegrees = defaultdict(int)


def topology(n: int) -> List[int]:
    dq = deque()
    for i in range(1, n + 1):
        if indegrees[i] == 0:
            dq.append(i)

    res = []
    while dq:
        node = dq.popleft()
        res.append(node)
        for neighbor in graph[node]:
            indegrees[neighbor] -= 1
            if indegrees[neighbor] == 0:
                dq.append(neighbor)

    if len(res) < n:
        return [0]
    else:
        return res


def main():
    def input():
        return stdin.readline().rstrip()

    n, m = map(int, input().split())
    for _ in range(m):
        order = list(map(int, input().split()))
        for i in range(1, len(order) - 1):
            graph[order[i]].append(order[i + 1])
            indegrees[order[i + 1]] += 1

    print(*topology(n), sep="\n")


if __name__ == "__main__":
    main()
トポロジーマップを使用してソートします.
各pdが歌手の順序を入力すると、graphおよびindegreesに次の歌手および入場順序が格納される.次に、入車数0の歌手を探して、順番を探します.