a091: 小群體
標籤 : 20170304Q2 APCS
通過比率 : 38人/38人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-26 17:36

內容

Q同學正在習程式, P老師出了以下的題目讓他練習。

一群人在一起時經常會形成一個一個的小群體。假設有 N個人,編號由 0到 N-1,每個人都寫下他最好朋友的編號(最好朋友有可能是他自己的編號,如果他自己沒有其他好友), 在本題中,每個人的好友編號絕對不會重複,也就是說0到 N-1每個數字 都恰好出現一次。

這種好友的關係會形成一些小群體。例如 N=10,好友編號如下,

自己編號

 0 

 1 

 2 

 3 

 4 

  5

 6 

 7 

 8 

 9 

好友編號

 4

 7

 2

 9

 6

 0

 8

 1

 5

 3

0的好友是 4,4的好友是 6,6的好友是 8,8的好友是 5,5的好友是 0,所以 0、4、 6、8、和 5就形成了一個小群體。另外, 1的好友是7而且7的好友是1,所以1和7形成另一個小群體,同理3和9是一個小群體,而2的好友是自己,因此他的好友是自己,因此他自己是一個小群體。總而言之在這個例子裡有4個小群體:{0,4,6,8,5}、{1,7} 、{3,9} 、 {2} 。本題的問題是:輸入每個人好友編號,計算出總共有幾小群體。

Q同學想了卻不知如何下手,和藹可親的P老師於是給了他以下的提示:如果你從任何一人x開始,追蹤他的好友,好友的好友,….,這樣一直下去,定會形成個圈回到 x,這就是一個小群體。如果我們追蹤的過程中把追蹤過的加以標記,很容易知道哪些人已經追蹤過,因此當一個小群體找到之後,我們再從任何還未蹤過的開始繼續找下一個小群體,直到所有人都追蹤完畢。

Q同學聽完之後很順利的成了作業。

在本題中,你的任務與Q同學一樣:給定群人的好友,請計算出小群體個數。

輸入說明

第一行是一個正整數N,說明團體中人數。

第二行依序是 0的好友編號 、1的好友編號 、…… 、N-1的好友編號。共有N個數字,包含 0到 N-1的每個數字恰好出現一次,數字間會有一個空白隔開。

輸出說明

請輸出小群體的個數。不要有任何多餘的字或空白,並以換行字元結尾。

範例輸入 #1
10
4 7 2 9 6 0 8 1 5 3
範例輸出 #1
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 :
標籤:
20170304Q2 APCS
出處:
APCS [管理者: ]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」