p015. 善意的循環
Tags :
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2025-06-23 17:57

Content

Life Vest Inside 是一個來自紐約的非營利組織,致力於推廣善意與助人文化。該組織製作了許多感人的影片,傳遞「微小善行也能產生巨大影響」的信念。

其中最廣為流傳的作品之一是 Kindness Boomerang – One Day。這是一支以「一鏡到底」手法拍攝的短片,沒有任何剪接,鏡頭流暢地串聯起一連串助人的行為。觀眾彷彿親身經歷了一場愛的接力,見證善意如何被一個人傳遞到另一人,最後又奇蹟般地回到起點。這部影片於 2011 年發布後迅速走紅,累積數千萬觀看次數,成為推廣「善意的循環」理念的經典。

正如影片所傳達的訊息,我們每一個人小小的善行,的確正悄悄地改變這個世界——即使你無法立刻看見它的迴響。

現在,給定一群人之間的助人關係,這些關係可構成一張有向圖(即「誰幫助了誰」),請你找出其中最短的一個「善行的循環」——也就是從某人出發,經過一連串助人行為,最後這股善意又回到原來的那個人。

Input

第一行為兩個整數 𝑛 與 𝑚 (1 ≤ 𝑛 ≤ 5×104, 1 ≤ 𝑚 ≤ 105),代表有 𝑛 個人(編號 1~𝑛),𝑚 筆助人行為。

接下來 𝑚 行,每行兩個整數 𝑎 和 𝑏,代表「𝑎 幫助了 𝑏」。

Output

一個整數:表示最短的「善意的循環」長度(即從某人出發回到自己,經過幾次幫助)。

若圖中不存在任何這樣的循環,輸出 -1。

Sample Input #1
5 6
1 2
2 3
3 1
4 5
5 4
3 4
Sample Output #1
2
Sample Input #2
4 3
1 2
2 3
3 4
Sample Output #2
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <1M
Hint :
Tags:
出處:
板橋高中教學題 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」