a445 - 新手訓練系列- 我的朋友很少

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個朋友關係的網路，給定 N 個人，M 個朋友關係，以及 Q 個詢問。對於每個詢問，需要判斷 P 和 Q 是否為朋友。朋友關係具有傳遞性，即如果 A 是 B 的朋友，B 是 C 的朋友，那麼 A 和 C 也是朋友。

解題思路

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

1. 初始化: 建立一個大小為 N+1 的陣列 a，其中 a[i] 初始化為 i。這表示每個元素最初都屬於自己的集合。
2. Union 操作: 對於每條朋友關係 (x, y)，找到 x 和 y 所屬的集合的根節點。如果根節點不同，則將一個集合的根節點指向另一個集合的根節點，表示合併這兩個集合。
3. Find 操作: 找到元素所屬集合的根節點。使用路徑壓縮優化，將路徑上的每個節點直接指向根節點，以提高後續查找的效率。
4. 查詢: 對於每個詢問 (x, y)，找到 x 和 y 所屬的集合的根節點。如果根節點相同，則 x 和 y 是朋友，輸出 ":)"; 否則，輸出 ":("。

複雜度分析

• 時間複雜度: O(M * α(N) + Q * α(N))，其中 α(N) 是反阿克曼函數，增長非常緩慢，可以視為常數。因此，時間複雜度近似於 O(M + Q)。
• 空間複雜度: O(N)，用於儲存 Disjoint Set 陣列 a。

程式碼

#include <iostream>
using namespace std;
int a[1000001]={0};
int ff(int n){
	if(a[n]==n)
		return n;
	return a[n]=ff(a[n]);
}
int main(){
	int N,M,Q;
	cin >> N >> M >> Q;
	for(int i=1;i<=N;i++)
		a[i]=i;
	while(M--){
		int x,y;
		cin >> x >> y;
		x = ff(x);
		y = ff(y);
		if(x!=y)
			a[y] = x; 
	}
	while(Q--){
		int x,y;
		cin >> x >> y;
		if(ff(x)==ff(y))
			printf(":)\n");	
		else
			printf(":(\n");
	}
}