L3-1 社交集群（30 分）

雨点打透心脏的1/2处 2022-05-29 14:09 200阅读 0赞

L3-1 社交集群（30 分）

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

### 输入格式： ###

输入在第一行给出一个正整数 N（≤1000），为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行，每行按以下格式给出一个人的兴趣爱好列表：

*K**i*: *h**i*\[1\] *h**i*\[2\] ... *h**i*\[*K**i*\]

其中*K**i*(>0)是兴趣爱好的个数，*h**i*\[*j*\]是第*j*个兴趣爱好的编号，为区间 \[1, 1000\] 内的整数。

### 输出格式： ###

首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

### 输入样例： ###

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

### 输出样例： ###

3
    4 3 1

并查集，暴力遍历使之连接就行了。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<vector>
    using namespace std;
    int father[1005];
    struct people
    {
    	int id,k;
    	int h[1005];
    }p[1005];
    int find(int x)  
    {  
    	int r=x,i=x,j;
    	while(father[r]!=r)
    	r=father[r];
    	while(father[i]!=i)
    	j=father[i],father[i]=r,i=j;
    	return r;
    }
    void combine(int a,int b) 
    {  
        int ta=find(a);  
        int tb=find(b);  
      	if(ta!=tb)  
       	father[ta]=tb;  
    }  
    int main()
    {
    	int t,n,m,i,j,k,l,sum=0;
    	map<int,int> ma;
    	scanf("%d",&t);
    	for(i=0;i<1005;i++)
    	father[i]=i;
    	for(j=1;j<=t;j++)
    	{
    		p[j].id=j;
    		scanf("%d:",&n);
    		p[j].k=n;
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&m);
    			p[j].h[i]=m;
    		}
    	}
    	for(i=1;i<=t;i++)
    	{
    		for(j=1;j<=t;j++)
    		{
    			int flag=0;
    			for(k=0;k<p[i].k;k++)
    			{
    				for(l=0;l<p[j].k;l++)
    				{
    					if(p[i].h[k]==p[j].h[l])
    					{
    						flag=1;
    						combine(i,j);
    						break;
    					}
    				}
    			}
    		}
    	}
    	for(i=1;i<=t;i++)
    	{
    		int ff=find(i);
    		if(i==ff)
    		sum++;
    		ma[ff]++;
    	}
    	printf("%d\n",sum);
    	int x[1005],o=0;
    	map<int,int>::iterator it;
    	for(it=ma.begin();it!=ma.end();it++)
    	{
    		x[o++]=it->second;
    	}
    	sort(x,x+o);
    	for(i=o-1;i>=0;i--)
    	{
    		if(i!=o-1)
    		printf(" ");
    		printf("%d",x[i]);
    	}
    	printf("\n");
    }