問題描述

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

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

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

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檔