c291 - APCS 2017-0304-2小群體

🔗 前往 ZeroJudge 原題

題目描述

題目描述一群人及其好友關係，要求計算小群體的數量。每個人的好友編號唯一，且範圍在 0 到 N-1 之間。小群體定義為通過好友關係追蹤，最終回到起點形成的循環。

解題思路

題目可以建模為一個圖，其中每個人的編號是節點，好友關係是邊。小群體相當於圖中的一個環。解題思路是遍歷所有節點，如果一個節點尚未被訪問，則從該節點開始追蹤其好友，直到回到起點，形成一個環。在追蹤過程中，將訪問過的節點標記為已訪問，避免重複計算。每次找到一個環，小群體數量加一。

複雜度分析

• 時間複雜度: O(N)，其中 N 是人數。因為每個節點最多被訪問一次。
• 空間複雜度: O(N)，用於儲存好友關係的陣列和標記訪問狀態的陣列。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b[50000],d=0,e=0,f;
	cin>>a;
	for(int c=0;c<a;c++){
		cin>>b[c];
	}
	for(int c=0;c<a;c++){
		if(b[c]!=-1){
			for(d=b[c];d!=-1;){
				f=d;
				d=b[d];
				b[f]=-1;
			}
			e++;
		}
	}
	cout<<e<<endl;
	return 0;
}