f167. m4a1-社團 Club - 高中生程式解題系統

內容

TOI練習賽 2020m4a1-社團 Club 原題連結

問題敘述
小明是高中社團幹部，負責向學校申請社團活動，然而申請過程十分繁雜，
他必須親自到多個處室跑流程。每當到一個處室時，他們可能會要求必須先經過
其他處室的核准。例如：小明如果要向總務處商借場地前，必須先經過學務處核
准活動的企劃案。於是小明紀錄下各個處室的要求，決定出申請的先後順序。
請寫一個程式幫助小明決定他到各個處室的先後順序。

評分說明
此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料，才能獲得該組分數，各組詳細限制如下。
第一組 ((10 分))：：N = 3
第二組 ((40 分))：：2 <= N <= 10
第三組 ((50 分))：：2 <= N <= 10^3

輸入說明

第一行有一個正整數 N ,2<=N<=10^3))，表示處室的數量，和一個整數 M [ N-1<=M<=Nx(N-1) ] 。接下來 M 行每行都有兩個正整數 a 和 b
(1<=a, b<=N)，代表處室的編號，表示必須先到 a 處室之後才可以到 b 處室。保證這個關係圖不會有重
複的邊，也就是 M 個 a, b 數對不會重複，而且也保證無論是否存在解答，關係圖為連通的，即不存在孤點。

輸出說明

第一行請輸出一個字串，如果存在解，輸出 YES ，否則就是行政人員在互相踢皮球，輸出 NO 。如果存在解，接下來請輸出 N 行，
每一行都有一個介於 1 ~N 正整數，為 1 ~N 的排列，代表小明在 N 個處室申請的先後順序越前面輸出為
越先到的處室。為了簡化問題，至多僅存在一個解。

範例輸入 #1

範例輸出 #1

YES
3
1
4
2

範例輸入 #2

範例輸出 #2

YES
4
1
5
2
3

範例輸入 #3

範例輸出 #3

NO

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

標籤:

拓樸排序

出處:

TOI練習賽 2020年 4月潛力組 [管理者： p3a_owhj (阿普二信) ]

編號	身分	題目	主題	人氣	發表日期
42564	s10900156@nh ... (ShanC)	f167		41	2024-10-02 21:59
37614	iamfelix (Felix)	f167	測資有重複邊	485	2023-09-19 23:46
29265	bubble60324@ ... (賢仔)	f167	新手的解題想法	558	2022-02-10 00:02
25514	fire5386 (becaidorz)	f167	Tarjan + 拓樸 + greedy	962	2021-05-28 09:46
22689	joeliao (RRRrrrr!!!)	f167	個人想法	1026	2020-09-25 00:37