L3-003 社交集群 （天梯赛）

首先一看就知道是并查集 但是其实这个题不简单

首先要把题目读清楚 一个集合 a b c 可能a和b b和c分别有交集 但是a和c没有交集

首先可以想到对拥有同一个兴趣爱好的人合并 这样 a和b b和c 都分别合并了

现在考虑将 ab整体 和 bc整体 合并 每个人作为b 依次将每个人的兴趣爱好合并即可

并查集还要统计并查集大小

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e3+5;
int fa[maxn],sz[maxn],ans[maxn];
int find(int x){
	if(x!=fa[x])return fa[x]=find(fa[x]);
	return x;
} 
void un(int x,int y){
	int fx=find(x),fy=find(y);
	fa[fx]=fy;
	if(fx!=fy)
	sz[fy]+=sz[fx];
	return;
}
int n,cnt;
int num[maxn],a[maxn][maxn];
vectorQ[maxn];
int main(){
	cin>>n;
	for(int i=1;i>num[i];
		char s;cin>>s;
		for(int j=1;j<=num[i];j++){
			cin>>a[i][j];
			Q[a[i][j]].push_back(i);
		}
	}
	for(int i=1;i=1;i--)
	cout<<" "<