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\n",cnt);
for (i=0; i<cnt; i++)
printf("%d%s",r[i],i==cnt-1?"\n":" ");
}
return 0;
}

秒客网

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

L3-003. 社交集群

相关文章