【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c291
【解題想法】
- 題目保證每個人的好友編號絕對不會重複。
- fr[ ]：紀錄每個人的好友編號。
- group[ ]：紀錄每個人所屬的群體。初始值為 -1。
- 每次發現一個還未檢查過的人，把他所屬的群體設為自己，然後開始把他的朋友，朋友的朋友….都加到同一個群體，直到形成一個環。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 50005;
int fr[maxn]; //friend
int group[maxn]; //group
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i=0; i<N; i++){
cin >> fr[i]; //紀錄每個人的好友編號
}
memset(group, -1, sizeof(group));
for (int i=0; i<N; i++){
if (group[i] >= 0) continue;
group[i] = i;
int now = i;
while (fr[now] != i){
group[fr[now]] = i;
now = fr[now];
}
}
int ans = 0;
for (int i=0; i<N; i++){
ans += (group[i] == i);
}
cout << ans << '\n';
return 0;
}
Python code
# 本題輸入包含若干筆測試資料
while True:
try:
N = int(input()) # 團體中人數
friend = list(map(int, input().split())) # 讀入每個人的好友編號
ans = 0
for i in range(N):
if friend[i] != -1: # 發現一個還未被檢查過的人
cur = i # cur (current): 目前受檢查者的編號
while True:
nxt = friend[cur] # nxt (next): 他的好友的編號
friend[cur] = -1 # 標註成檢查過了
if nxt == i: # 形成一個環
break
cur = nxt # 繼續檢查朋友的朋友
ans += 1
print(ans)
except:
break