a538:
[模板] 拓樸排序
標籤
:
kahn's algorithm
priority queue
通過比率 : 1人/2人 ( 50% ) [非即時]
評分方式：
最近更新 : 2024-11-01 23:43
通過比率 : 1人/2人 ( 50% ) [非即時]
評分方式：
Tolerant
最近更新 : 2024-11-01 23:43
內容
班上有 $n$ 個小朋友要排隊，為了讓小朋友們開心，老師允許每個小朋友列出願望清單，寫出想要有誰站在他的前面 (願望清單裡可以不只一個人，有可能出現重複的人，但不會出現自己)。
但有時候未必能如大家所願，因此老師希望你可以幫忙寫一個程式來分配隊伍，對於每個小朋友，他的願望清單裡的所有人都要排在他的前面，才算滿足條件。
為了更好的控管學生，老師希望可以獲得字典序最小的合法排隊方案，請輸出字典序最小的合法排隊方案 (保證至少存在一種合法的排隊方案)。
輸入說明
輸入第一行將有一個整數 $n(1≤n≤10^5)$，代表小朋友的數量，接下來會有 $n$ 行，第 $i$ 行的第一個數字為 $m_i(0≤m_i≤n−1)$，代表願望清單裡有幾個人，緊接著就是 $mi$ 個介於 $1∼n$ 的整數代表朋友的編號 $a_{i,1},a_{i,2},…,a_{i,m_i}$。$(\sum_{i=1}^{n}m_i≤2×10^5)$
輸出說明
請輸出 $n$ 個數字 $ans_1 ans_2 \dots ans_n$，代表字典序最小的排隊方案。
範例輸入
#1
5 1 3 1 1 0 0 1 4
範例輸出
#1
3 1 2 4 5
範例輸入
#2
6 0 1 1 1 1 2 6 3 4 3 2 4 1 0
範例輸出
#2
1 2 3 6 4 5
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
出處:
APCS模擬賽
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 121 | a538 | 40 | 2024-11-01 23:48 |