c291: APCS 2017-0304-2小群體
標籤 : APCS
通過比率 : 92% (58 人 / 63 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-10-06 22:19

內容

問題描述

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同學一樣:給定群人的好友,請計算出小群體個數。

原題pdf檔

輸入說明

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

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

輸出說明

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

範例輸入
範例一:輸入
10
4 7 2 9 6 0 8 1 5 3
範例二:輸入
3
0 2 1
範例輸出
範例一:正確輸出
4
範例二:正確輸出 
2
測資資訊:
記憶體限制: 256 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 , <1M
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#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
提示 :

(範例一說明)

4個小群體是 {0,4,6,8,5 }, {1,7 }, {3,9 }和 {2}。

(範例二說明)

2個小 群體分別是 {0},{1,2 }。

評分說明

輸入包含若干筆測試資料,每一的執行時間限制(time limit)均為1秒,依正確通過測資筆 數給分。 其中:

第 1子題組 20分, 1 ≤ N ≤  100 ,每一個小群體不超過 2人。

第 2子題組 30 分, 1 ≤ N ≤  1,000 ,無其他限制 。

第 3子題組 50分, 1,00 1 ≤ N ≤  50,000 ,無其他限制 。

測資非官方的,是我自己產生的,若有誤請不吝告知

標籤:
APCS
出處:
2017年3月APCS [編輯:
p3a_owhj (阿普二信)
]


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