---
# System prepended metadata

title: APCS小群體
tags: [APCS, 解析]

---

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

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

**自己編號 0123456789
朋友編號 4729608153**


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的每個數字恰好出現一次，數字間會有一個空白隔開。
https://zerojudge.tw/ShowProblem?problemid=c291
:::
***
這題我是先找出某人(起點)的朋友，在找出朋友的朋友，直到找回起點
***
**引入標頭檔**
```cpp=
#include <iostream>
using namespace std;
```
***
**宣告題目所需的變數**
```cpp=
int n=0, ans=0;
cin >> n;
```
***
**接著宣告兩個陣列(大小為n)來儲存 ==本身== 跟 ==朋友== 的編號**
```cpp=
int* people = new int[n];
int* fri = new int[n];
```
***
**輸入每個人朋友的編號，並將 ==本身== 的陣列也設定好**
```cpp=
for(int i=0;i<n;i++)
 {
     cin >> fri[i];
     people[i] = i; //本身
 }
```
***
**開始尋找**
```cpp=
 for(int i=0;i<n;i++)
 {   
    int i1 = i; //設一個暫存的數i1存i
    if(people[i] != -1)  //-1代表被找過
    {
		while(people[i] != fri[i1])
 		{
			
			for(int j=0;j<n;j++)
			{
		 		if(fri[i1] == people[j])
		 		{
		 			people[j] = -1;
		 			i1 = j;
		 			break;
				}
			}
                }
	people[i] = -1;
 	ans++;
    }
 }
```
首先 i=0 開始找1號 ==people[ i ]== 的朋友 也就是 ==fri[ i ]==， ==i1是用來尋找的變數，初始為i==
接著用for迴圈把people陣列都跑一遍，如果 ==people[ j ]== 等於 ==fri[ i1 ]== 
就把people[ j ]設為-1(防止重複尋找)並把i1設成j繼續下一次的尋找，全部找完後就把起點設為-1、ans+1

最後輸出ans
***
:::success
完整程式碼
:::
```cpp=
//APCS小群體
#include <iostream>
using namespace std;
int main()
{
 int n=0, ans=0;
 cin >> n;
 int* people = new int[n];
 int* fri = new int[n];
 for(int i=0;i<n;i++)
 {
     cin >> fri[i];
     people[i] = i;
 }
 for(int i=0;i<n;i++)
 {   
   int i1 = i;
    if(people[i] != -1)  
   	{
		while(people[i] != fri[i1])
 		{
			
				for(int j=0;j<n;j++)
				{
		 			if(fri[i1] == people[j])
		 			{
		 				people[j] = -1;
		 				i1 = j;
		 				break;
					}
				}
		}
		people[i] = -1;
 	    ans++;
   	}
 }
  cout << ans << "\n";
  return 0;
}
```
:::success
掰掰 :D
:::

