f167: m4a1-社團 Club
Tags : 拓樸排序
Accepted rate : 10人/13人 ( 77% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-08-04 22:46

Content

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

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

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

Input

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

Output

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

 

Sample Input #1
4 3
1 4
4 2
3 1
Sample Output #1
YES
3
1
4
2
Sample Input #2
5 6
1 5
5 2
2 3
1 2
4 1
4 5
Sample Output #2
YES
4
1
5
2
3
Sample Input #3
5 7
1 5
5 2
2 3
2 1
4 1
4 3
4 5
Sample Output #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
Hint :
Tags:
拓樸排序
出處:
TOI練習賽2020年4月潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
22689
joeliao (RRRrrrr!!!)
f167
個人想法
15 2020-09-25 00:37