Editorial for 小群體 (APCS 2017-03 中級)
簡潔題意
\(N\) 個人編號 \(0 \sim N - 1\),每個人寫下最好朋友的編號(可以是自己),而且 \(0 \sim N - 1\) 每個編號恰好出現一次。從任何人出發沿著好友、好友的好友一直追,一定會繞一圈回到自己——這一圈就是一個小群體。輸出小群體的個數。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(20\) 分):\(N \le 100\),每個小群體最多 \(2\) 人。
- 子題組 2(\(30\) 分):\(N \le 1000\)。
- 子題組 3(\(50\) 分):\(N \le 50000\)。
先拿下子題組 1(20 分):群體最多兩個人,直接問
每個小群體最多兩人,只有兩種長相:一個人(好友是自己,best[i] == i)、兩個人互為好友(best[best[i]] == i)。把好友編號讀進一維陣列 best[](上冊 6.1),掃一遍 \(0 \sim N - 1\):好友是自己就加一;兩人一組的,\(i\) 和 best[i] 兩邊都會各看到一次,所以只在編號小的那一邊算(i < best[i]),不然會算成兩倍。
#include <iostream>
using namespace std;
const int MAX_N = 50000;
int main() {
int n;
cin >> n; // 子題組 1 保證每個小群體最多 2 人
int best[MAX_N]; // best[i]=編號 i 的人寫的最好朋友(陣列照題目最大的 N 開,免得別的子題組讀入時寫到外面)
for (int i = 0; i < n; i++) cin >> best[i];
int groups = 0;
for (int i = 0; i < n; i++) {
if (best[i] == i) { // 好友是自己:一個人的小群體
groups++;
} else if (best[best[i]] == i && i < best[i]) { // 兩個人互為好友:只在編號小的那一邊算一次
groups++;
}
}
cout << groups << '\n';
return 0;
}
陣列大小照題目最大的 \(N\) 開(\(50000\) 個 int 才 \(200\) KB,上冊 6.10),只開 \(100\) 的話子題組 2、3 讀入時就寫到陣列外面。這份程式交上去,範例 1(有五個人的群)和子題組 2、3 大多會 WA——這是正常的,逐筆給分之下子題組 1 的 \(20\) 分穩穩到手。
從 20 分到 100 分:追蹤一圈、沿路做記號
三個人以上的群沒辦法用幾個 if 問完,但題目裡 P 老師已經把做法講完了:從還沒追蹤過的人出發,沿著好友一直追,追過的人做記號;追到碰上做過記號的人就是繞完一圈——那是一個小群體;再找下一個還沒有記號的人出發。程式只需要兩樣東西:
- 一張「追蹤過了沒」的標記表
visited(vector<bool>,10.2;上冊 6.7 用陣列記錄資訊的同一招)。 - 一個
while(上冊 4.2):x還沒記號就蓋章、跳到best[x],碰到有記號的人停下來。外層for掃 \(0 \sim N - 1\),看到沒記號的 \(i\) 就groups++、從它追一圈。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> best(n); // best[i]=編號 i 的人寫的最好朋友
for (int i = 0; i < n; i++) cin >> best[i];
vector<bool> visited(n, false); // 追蹤過了沒
int groups = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue; // 已經在某個小群體裡,跳過
groups++; // 還沒追蹤過:從 i 開始是一個新的小群體
int x = i;
while (!visited[x]) { // 沿著好友一路追,追到回到已標記的人為止
visited[x] = true;
x = best[x];
}
}
cout << groups << '\n';
return 0;
}
為什麼一定要做記號?不做記號也能寫——每個人各自繞一圈、只在自己是圈裡最小編號時算一次,這樣子題組 2 還過得了;但每個人都繞完整圈,\(N = 50000\) 的人全在同一圈時要繞 \(50000 \times 50000 = 2.5 \times 10^9\) 步(本站實測 \(4.5\) 秒,上冊 4.9 的估法)。做了記號,每個人只會被追到一次,總共 \(N\) 步,一瞬間。
測過再交:範例沒有「全部同一圈」和「全部各自一群」
範例 1 是一群五人加幾個小群、範例 2 是一個人加一對。補兩個極端、一個大的:
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 / 0 |
1 |
只有一個人、好友是自己 |
3 / 0 1 2 |
3 |
每個人都是自己一群 |
5 / 1 2 3 4 0 |
1 |
全部同一圈:只數「好友是自己」或只處理兩人一組的程式印 0 |
4 / 1 0 3 2 |
2 |
兩對互為好友:子題組 1 版就能驗 |
50000 / 1 2 3 … 49999 0(用程式產生) |
1 |
五萬人一個大圈:不做記號、每人各自繞一圈的程式要 \(4.5\) 秒,子題組 3 會 TLE |
五筆都親眼看過正確,這題就穩了。
常犯錯誤
- 只數「好友是自己」的人:範例 1 印
1(該印4)。 - 只處理一人和兩人的群:範例 1 印
3;自測表第 3 列印0。 - 追蹤時只對起點做記號、沒把整圈標完:圈裡其他人之後又各自被當成新的群——範例 1 印
10。 - 不做記號、每個人各自繞一圈:答案對但太慢——自測表第 5 列要 \(4.5\) 秒,子題組 3 TLE。
- 陣列只開 \(100\)(子題組 1 的上限):子題組 2、3 讀入時寫到陣列外面、程式當掉。