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的每個數字恰好出現一次,數字間會有一個空白隔開。
請輸出小群體的個數。不要有任何多餘的字或空白,並以換行字元結尾。
10 4 7 2 9 6 0 8 1 5 3
4
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |