1107 social clusters (30 points)

The main idea of the topic ： Everyone likes some hobbies , Those who have the same hobbies are considered as a group , Number of output groups , And the number of people in each group , From large to small output .

Transform the meaning of the question to find the number of connected blocks , And the number of points in the block . Don't mix the hobby number with the person number here , We mark our hobbies with human labels , Then there is the merge set template .

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1000;
int p[N],st[N];
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main()
{	
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i ++) p[i] = i;
	for(int i = 1; i <= n; i ++)
	{
		int k;
		scanf("%d:",&k);
		for(int j = 0 ; j < k; j ++)
		{
			int x;
			cin >> x;
			if(!st[x]) st[x] = i;// The number is i People like it j This activity 
			int a = find(i),b = find(st[x]);
			if(a != b) p[a] = b;
		}
	}
	vector<int>ans(n + 1,0);int cnt = 0;
	for(int i = 1; i <= n; i ++) ans[find(i)] ++;
	for(auto it : ans) if(it != 0) cnt ++;
	sort(ans.begin(),ans.end(),[](int a,int b)
	{
		return a > b;
	});
	cout << cnt << '\n';
	for(int i = 0; i < cnt; i ++)
	{
		if(i != 0) cout << ' ';
		cout << ans[i];
	}
	return 0;
}