# APCS實作題2017年3月第2題：小群體
> 第1版：2023年2月14日
> 第2版：2023年6月10日，新增 C++ 程式碼
> 作者：王一哲
> 題目來源：[106年3月4日實作題第2題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1060304APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c291)
<br />
## 題目
### 問題描述
Q 同學正在學習程式，P 老師出了以下的題目讓他練習。
一群人在一起時經常會形成一個一個的小群體。假設有 N 個人，編號由 0 到 N-1，每個人都寫下他最好朋友的編號（最好朋友有可能是他自己的編號，如果他自己沒有其他好友），在本題中，**每個人的好友編號絕對不會重複，也就是說 0 到 N-1 每個數字都恰好出現一次**。
這種好友的關係會形成一些小群體。例如 N = 10，好友編號如下
<center>
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ------ | - | - | - | - | - | - | - | - | - | - |
| 好友編號 | 4 | 7 | 2 | 9 | 6 | 0 | 8 | 1 | 5 | 3 |
</center>
<br />
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 同學一樣：給定一群人的好友，請計算出小群體個數。
<br />
### 輸入格式
第一行是一個正整數 N，說明團體中人數。
第二行依序是 0 的好友編號、1 的好友編號、……、N-1 的好友編號。共有 N 個數字，包含 0 到 N-1 的每個數字恰好出現一次，數字間會有一個空白隔開。
<br />
### 輸出格式
請輸出小群體的個數。不要有任何多餘的字或空白，並以換行字元結尾。
<br />
### 範例一：輸入
```
10
4 7 2 9 6 0 8 1 5 3
```
### 範例一：正確輸出
```
4
```
（說明）4 個小群體是 {0, 4, 6, 8, 5}, {1, 7}, {3, 9}和{2}。
<br />
### 範例二：輸入
```
3
0 2 1
```
### 範例二：正確輸出
```
2
```
（說明）2 個小群體分別是{0}, {1, 2}。
<br />
### 評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。其中：
- 第 1 子題組 20 分，$1 \leq N \leq 100$，每一個小群體不超過 2 人。
- 第 2 子題組 30 分，$1 \leq N \leq 1,000$，無其他限制 。
- 第 3 子題組 50 分，$1,001 \leq N \leq 50,000$，無其他限制。
<br />
## Python 程式碼
```python=
N = int(input()) # 人數
friends = list(map(int, input().split())) # 好朋友資料
visited = [False]*N # 是否已經讀過這筆資料
count = 0 # 小群體數量
#group = [] # 小群體資料，二維串列，除錯用
for i in range(N):
while not visited[i]:
visited[i] = True
#group.append([i])
if friends[i] == i:
pass
else:
j = friends[i]
visited[j] = True
#group[-1].append(j)
j = friends[j]
while not visited[j]:
visited[j] = True
#group[-1].append(j)
j = friends[j]
count += 1
#print(group)
print(count)
```
<br />
1. 第7 ~ 22行：使用 for 迴圈將資料完整地跑過一次。
2. 第8 ~ 22行：於 for 迴圈中的 while 迴圈，如果這筆資料還沒有讀過時繼續運作。先將這筆資料的狀態改成已讀過。接下來有兩種可能的狀況：
1. 第11、12行：自己是一個小群體，pass，不做任何事。
2. 第13 ~ 21行：先找到 i 的朋友 j，將 j 的狀態改成已讀過；再找 j 的朋友，覆蓋掉 j 原來的值；使用 while 迴圈重複以上3行，直到讀過所有資料。如果使用 C 或 C++ 解題，可以使用 do while 迴圈，但是 Python 沒有 do while 迴圈，所以在 while 迴圈前先跑一次同樣的步驟。
外層的 while 迴圈執行一次，代表找到一個小群體中所有的成員，小群體數量 count 加1。
3. 第5、10、16、20、24行：這幾行是除錯用的工具，將小群體的成員儲存在二維串列 group，提交程式碼測試時要註解或刪除。如果測資為
```
10
4 7 2 9 6 0 8 1 5 3
```
group 最後印出的內容為
```python
[[0, 4, 6, 8, 5], [1, 7], [2], [3, 9]]
```
4. 於 ZeroJudge 測試結果，第10筆測資花費時間最久，約 61 ms，使用記憶體 9.2 MB，通過測試。
<br /><br />
## C++ 程式碼
```cpp=
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
// 由標準輸入讀取好友資料筆數 N、好友資料 friends
int N;
cin >> N;
int friends[N], visited[N] = {0}, count = 0;
for(int i=0; i<N; i++) {
cin >> friends[i];
}
for(int i=0; i<N; i++) {
while(visited[i] == 0) {
visited[i] = 1;
if (friends[i] == i) {
;
} else {
int j = friends[i];
do {
visited[j] = 1;
j = friends[j];
} while(visited[j] == 0);
}
count++;
}
}
cout << count << endl;
return 0;
}
```
<br />
1. 第6 ~ 11行：由標準輸入讀取讀取好友資料筆數 N、好友資料 friends。
2. 第13 ~ 27行：使用 for 迴圈將資料完整地跑過一次。
3. 第14 ~ 26行：於 for 迴圈中的 while 迴圈，如果這筆資料還沒有讀過時繼續運作。先將這筆資料的狀態改成已讀過。接下來有兩種可能的狀況：
1. 第16、17行：自己是一個小群體，不做任何事。
2. 第18 ~ 24行：使用 do while 迴圈，先找到 i 的朋友 j，將 j 的狀態改成已讀過；再找 j 的朋友，覆蓋掉 j 原來的值，直到讀過所有資料。
外層的 while 迴圈執行一次，代表找到一個小群體中所有的成員，小群體數量 count 加1。
4. 於 ZeroJudge 測試結果，花費時間為 39 ms，使用記憶體 704 kB，通過測試。
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet