c291. APCS 小群體

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)

相關文章

分享此文：