f630 - 5. 共同朋友

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個社交網絡，其中每個人的朋友列表已知。要求計算有多少對朋友具有共同的朋友。

解題思路

這題的核心是計算每對人之間共同朋友的數量。程式使用 bitset 來表示每個人的朋友關係，其中 bitset 的每個位元代表一個人是否為該人的朋友。edg[i] 表示第 i 個人擁有的朋友集合。

程式遍歷所有可能的兩人組合 (i, j)，其中 i < j。對於每對組合，使用 & 運算符計算 edg[i] 和 edg[j] 的交集，得到他們的共同朋友集合。如果共同朋友集合非空（即 jd.any() 為真），則將答案 ans 增加 1。

使用 bitset 的優點是它可以高效地進行集合的交集運算。

複雜度分析

• 時間複雜度: O(n^2 * m)，其中 n 是人數，m 是最多朋友數。外層兩個迴圈遍歷所有可能的兩人組合，時間複雜度為 O(n^2)。內層計算交集的時間複雜度為 O(m)，因此總時間複雜度為 O(n^2 * m)。
• 空間複雜度: O(n * m)，其中 n 是人數，m 是最多朋友數。edg 陣列儲存了每個人的朋友關係，每個 bitset 的大小為 m，因此總空間複雜度為 O(n * m)。

程式碼

#include <iostream>
#include <bitset> 
using namespace std;
int n,ans,x,ct,d,cn;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	bitset <2505> edg[2505];
	for(int i=0;i<n;++i){
		cin >> d;
		edg[i].reset();
		for(int j=0;j<d;++j){
			cin >> x;
			edg[i].set(x-1);
		}
	}
	for(int i=0;i<n;++i)
		for(int j=i+1;j<n;++j){
			bitset <2505> jd(edg[i]&edg[j]);
			if(jd.any())++ans;
		}
	cout << ans;
}