f167. m4a1-社團 Club
標籤 : 拓樸排序
通過比率 : 220人/236人 ( 93% ) [非即時]
評分方式:
Tolerant

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

內容

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
4 3
1 4
4 2
3 1
範例輸出 #1
YES
3
1
4
2
範例輸入 #2
5 6
1 5
5 2
2 3
1 2
4 1
4 5
範例輸出 #2
YES
4
1
5
2
3
範例輸入 #3
5 7
1 5
5 2
2 3
2 1
4 1
4 3
4 5
範例輸出 #3
NO
測資資訊:
記憶體限制: 64 MB
提示 :
標籤:
拓樸排序
出處:
TOI練習賽2020年4月潛力組 [管理者: p3a_owhj (阿普二信) ]

本題狀況 本題討論 排行

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