2023.1.24 PM 10:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=c291 出題者 : 2017年3月APCS 標籤 : 遞迴、多分圖 難易度 : 2
解題想法 : 可以把每次找小群體包成一個函式,答案就是跑這個函式的次數。 可以維護一個陣列visited[],紀錄每個index走訪的情形,假如visited[index]=true,表示已經走過編號為index的位置,可以透過這個陣列來得到函式的終止點。
#include<stdio.h>
int friends[50005];
int visited[50005]={0};
void find(int cur){
visited[cur]=1;
while(!visited[friends[cur]]){
cur=friends[cur];
visited[cur]=1;
}
}
int main(){
int N;
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d",&friends[i]);
}
int ans=0;
for(int i=0;i<N;i++){
if(!visited[i]){
find(i);
ans++;
}
}
printf("%d\n",ans);
return 0;
}

//C++ language
#include<iostream>
#include<vector> //vector
using namespace std;
vector<int> friends;
vector<bool> visited;
void find(int cur){
visited[cur]=true;
while(!visited[friends[cur]]){
cur=friends[cur];
visited[cur]=true;
}
}
int main(){
int N; cin>>N;
friends.resize(N);
visited.assign(N,false);
for(int &i:friends) cin>>i;
int ans=0;
for(int i=0;i<N;i++){
if(!visited[i]){
find(i);
ans++;
}
}
cout<<ans<<"\n";
return 0;
}

## Python language
N=int(input())
friends=[int(x) for x in input().split()]
visited=[False]*N
def find(cur):
visited[cur]=True
while not visited[friends[cur]]:
cur=friends[cur]
visited[cur]=True
ans=0
for i in range(N):
if not visited[i]:
find(i)
ans+=1
print(ans)
