小群體 (APCS 2017-03 中級)

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

輸入格式

第一行是一個正整數 \(N\)，說明團體中人數。

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

輸出格式

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

範例輸入 1

10
4 7 2 9 6 0 8 1 5 3

範例輸出 1

4

範例解釋 1

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

範例輸入 2

3
0 2 1

範例輸出 2

2

範例解釋 2

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

評分說明

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

第 1 子題組 20 分：\(1 \le N \le 100\)，每一個小群體不超過 2 人。

第 2 子題組 30 分：\(1 \le N \le 1,000\)，無其他限制。

第 3 子題組 50 分：\(1,001 \le N \le 50,000\)，無其他限制。

題目來源

APCS 2017 年 3 月 4 日實作題第 2 題「小群體」。參考 APCS 官方歷屆試題 PDF 與 ZeroJudge c291。