d808 - 黑暗部落

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算黑暗大陸上野人部落的數量以及最大部落的人數。輸入給定每個野人與哪個野人屬於同一部落的資訊，需要從這些資訊中推斷出部落的構成。

解題思路

本題可以使用 Union-Find (也稱為 Disjoint Set) 演算法來解決。Union-Find 演算法用於處理不相交集合的合併和查找操作。

1. 初始化: 建立一個 fa 陣列，其中 fa[i] 表示野人 i 的父節點。初始時，每個野人都是一個獨立的部落，因此 fa[i] = i。同時，建立一個 sz 陣列，其中 sz[i] 表示以野人 i 為根的部落的大小。初始時，每個部落的大小都為 1。
2. 合併: 遍歷輸入的資訊，對於每條資訊 x, i，表示野人 i 與野人 x 屬於同一部落。使用 ff 函數找到野人 i 和 x 的根節點。如果根節點不同，則將較小的部落合併到較大的部落中，更新 fa 和 sz 陣列。
3. 計算部落數量和最大部落大小: 在合併過程中，記錄合併的次數 ct。最終，部落的數量為 n - ct。在合併過程中，更新最大部落的大小 ans。

ff 函數使用路徑壓縮優化，以提高查找效率。合併操作使用按大小合併優化，以避免樹的深度過大，進而提高效率。

複雜度分析

• 時間複雜度: O(n α(n))，其中 n 是野人的數量，α(n) 是反阿克曼函數，增長非常緩慢，可以視為常數。
• 空間複雜度: O(n)，用於儲存 fa 和 sz 陣列。

程式碼

#include <iostream>
using namespace std;
int fa[1000001],sz[1000001],n,ans,ct,x;
int ff(int x){
	if(fa[x]==x)return x;
	return fa[x]=ff(fa[x]);
}
void mg(int x,int y){
	x=ff(x);
	y=ff(y);
	if(x==y)return;
	if(sz[x]<sz[y]){
		swap(x,y);
	}
	sz[x]+=sz[y];
	ans=max(ans,sz[x]);
	++ct;
	sz[y]=0;
	fa[y]=x;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> n){
		ans=ct=0;
		for(int i=1;i<=n;++i){
			fa[i]=i;
			sz[i]=1;
		}
		for(int i=1;i<=n;++i){
			cin >> x;
			mg(x,i);
		}
		cout << n-ct << " " << ans << '\n';
	}
}