PAT天梯赛练习题——L3-003. 社交集群（并查集按秩合并）

L3-003. 社交集群

时间限制

1000 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。

输入格式：

输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好：

K_i: h_i[1] h_i[2] ... h_i[K_i]

其中K_i（>0）是第i个人的兴趣的数量，h_i[j]是第i个人的第j项兴趣的编号，编号范围为[1, 1000]内的整数。

输出格式：

首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

输出样例：

3
4 3 1

似乎挺简单的跟Suspects一样的题目，一遍水过

代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
const int N=1010;
vector<int>person[N];
map<int,vector<int> >belong;
int pre[N],ran[N],r[N];
void init()
{
	for (int i=0; i<N; i++)
	{
		person[i].clear();
		pre[i]=i;
		ran[i]=1;
	}	
	belong.clear();
	MM(r);
}
inline int find(int n)
{
	if(n!=pre[n])
		return pre[n]=find(pre[n]);
	return pre[n];
}
inline int joint(int a,int b)
{
	int fa=find(a),fb=find(b);
	if(fa==fb)
		return 0;
	if(fa>=fb)
	{
		pre[fb]=fa;
		ran[fa]+=ran[fb];
		ran[fb]=0;
		return 1;
	}
	else
	{
		pre[fa]=fb;
		ran[fb]+=ran[fa];
		ran[fa]=0;
		return 1;
	}
}
bool cmp(const int &a,const int &b)
{
	return a>b;
}
int main(void)
{
	int n,i,j,h,a,b,m,k;
	while (~scanf("%d",&n))
	{
		init();
		for (i=1; i<=n; i++)
		{
			scanf("%d:",&m);
			for (j=1; j<=m; j++)
			{
				scanf("%d",&h);
				person[i].push_back(h);
				belong[h].push_back(i);
			}
		}
		
		for (i=1; i<=n; ++i)
		{
			for (j=0; j<person[i].size(); ++j)
			{
				int hobb=person[i][j];
				for (k=0; k<belong[hobb].size(); k++)
				{
					int oth=belong[hobb][k];
					joint(i,oth);
				}
			}
		}
		int cnt=0;
		for (i=1; i<=n; i++)
		{
			if(ran[i]!=0)
				r[cnt++]=ran[i];
		}		
		sort(r,r+cnt,cmp);
		printf("%d
",cnt);
		for (i=0; i<cnt; i++)
			printf("%d%s",r[i],i==cnt-1?"
":" ");
	}
	return 0;
}