# 實作題 - 小群體 - APCS - by Peter Wang
## 題目資訊
此題為2017.3.4測驗中的題目2
###### tags: `APCS` `遞迴`

## 題目敘述

假設有*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}* 。

### 輸入：
第一行是一個正整數*N*，說明團體中人數。

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

### 輸出：
請輸出小群體的個數。

## 解題思路
isin 來記錄是否已經進去過。
跑過一次遞迴ans++，最後就能算出答案。

## 程式碼

#include <iostream>
using namespace std;

int arr[50004];
bool isin[50004];
int ans=0;

void r(int p){
	if(isin[p]==true) return;
	isin[p]=true;
	r(arr[p]);
}

int main(){
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		fill(isin,isin+n,false);
		for(int i=0;i<n;i++){
			if(isin[i]) continue;
			r(arr[i]);
			ans++;
		}
		cout<<ans<<endl;
	}
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=c291)
[原題PDF檔](https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx6c2dpdGl0aXR8Z3g6MTRmYzQ0ZTM0MzJjZTlhYQ)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 9:58 AM]