[python]伯俊2623-音楽番組の解答
8501 ワード
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の歌手を探して、順番を探します.Reference
この問題について([python]伯俊2623-音楽番組の解答), 我々は、より多くの情報をここで見つけました https://velog.io/@boorook/Python-백준-2623-음악프로그램-문제-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol