PAT.A1107 Social Clusters

返回目录

题意

有N个人，每个人喜欢若干项活动，如果两个人有任意一一个活动相同，那么就称他们处于同一个社交网络(若A和B属于同一个社交网络，B和C属于同一个社交网络，那么A、B、C属于同一个社交网络)。求这N个人总共形成了多少个社交网络。

样例（可复制）

8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4

//output
3
4 3 1

注意点

1. 本题使用并查集的思想，将每个集合设定一个根节点，每个新加入的人要么加入原有的根节点，要么新建一个新的根节点

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
//root存放每个编号对应的根节点，flag标记活动第一个喜欢的人的编号，isroot存放某个节点作为活动根节点中参与的人数 
int root[N],flag[N]={0},isroot[N]={0};
int findroot(int a){
	while(a!=root[a])a=root[a];
	return a;
}
void Union(int a,int b){
	int roota=findroot(a);
	int rootb=findroot(b);
	if(roota!=rootb)root[roota]=rootb;
}
bool cmp(int a,int b){
	return a>b;
}
int main(){
	int n,k,h;
	cin>>n;
	for(int i=0;i<=n;i++)root[i]=i;
	for(int i=1;i<=n;i++){
		scanf("%d:",&k);
		while(k--){
			scanf("%d",&h);
			if(flag[h]==0)flag[h]=i;
			Union(i,findroot(flag[h]));
		}
	}
	for(int i=1;i<=n;i++)isroot[findroot(i)]++;
	int count=0;//集合数
	for(int i=0;i<=n;i++){
		if(isroot[i]!=0)count++;
	} 
	printf("%d\n",count);
	sort(isroot+1,isroot+n+1,cmp);
	for(int i=1;i<=count;i++){
		printf("%d",isroot[i]);
		if(i<count)printf(" ");
	}
    return 0;
}