1107 Social Clusters (30 分) 并查集

た入场券 2021-11-01 12:20 252阅读 0赞

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A **social cluster** is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

### Input Specification: ###

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

Ki: hi\[1\] hi\[2\] ... hi\[Ki\]

where Ki (>0) is the number of hobbies, and hi\[j\] is the index of the j-th hobby, which is an integer in \[1, 1000\].

### Output Specification: ###

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

### Sample Input: ###

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

### Sample Output: ###

3
    4 3 1

**题意：**n个人，每个人有k个爱好，分别是...

爱好有一个相同即为同一团体的人

输出团体个数，每个团体包含的人数(从大到小)

**思路：**暴力循环把每个人的爱好遍历，有与之相同的就combine

find(i)找到祖先，祖先相同则为同一个团体

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int ma[1005][1005];
    int fa[1005];
    vector<int> ha[1005];
    int find(int x)
    {
    	int r=x,i=x,j;
    	while(fa[r]!=r)
    	r=fa[r];
    	while(fa[i]!=i)
    	j=fa[i],fa[i]=r,i=j;
    	return r;
    }
    void combine(int x,int y)
    {
    	int xx=find(x);
    	int yy=find(y);
    	if(xx<yy)
    	fa[yy]=xx;
    	else
    	fa[xx]=yy;
    }
    int main()
    {
    	int n,m,k,i,j,l,p;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	{
    		fa[i]=i;
    		scanf("%d:",&m);
    		for(j=0;j<m;j++)
    		{
    			scanf("%d",&k);
    			ha[i].push_back(k);
    		}
    	}
    	for(i=1;i<=n;i++)
    	{
    		for(j=0;j<ha[i].size();j++)
    		{
    			for(l=1;l<=n;l++)
    			{
    				for(p=0;p<ha[l].size();p++)
    				{
    					if(ha[i][j]==ha[l][p])
    						combine(i,l);
    				}
    			}
    		}
    	}
    	int num[1005]={0};
    	for(i=1;i<=n;i++)
    	{
    		num[find(i)]++;
    		//printf("%d : %d\n",i,find(i));
    	}
    	vector<int> res;
    	for(i=1;i<=n;i++)
    	{
    		if(num[i])
    		res.push_back(num[i]); 
    	}
    	sort(res.begin(),res.end());
    	printf("%d\n",res.size());
    	for(i=res.size()-1;i>0;i--)
    	printf("%d ",res[i]);
    	printf("%d\n",res[0]);
    }