|并查集 与谁合并？|1107 Social Clusters (30分)

1107 Social Clusters (30分)

link比如7
很有可能 7是爱好6 8 1 的领头羊(第一个喜欢的)
（后面爱好6 8 1的人会和7在一个组）
但是 7 也是 爱好5 的小喽喽
（所以7和爱好5的领头羊2 在一个组）
（原本因为爱好6 8 1跟随7的小喽喽 也会和2在一个组）

int main() {
	int n, k, h;
	cin >> n;
	init(n);//人的编号从1开始//1.初始化
	for (int i = 1; i <= n; i++) {
		scanf_s("%d:", &k);//活动个数
		for (int j = 0; j < k; j++) {
			cin >> h;//输入第i好人喜欢的活动
			if (course[h] == 0) {//如果活动h第一次有人喜欢
				course[h] = i;//令i喜欢活动h
			}
			Union(i,findFather(course[h]));//对于当前读入的人的编号i和他喜欢的每1个活动，合并findFather(course[h])
			//Union(i,course[h]);
		}
	}

sort(isRoot + 1, isRoot + n + 1, cmp);//人的编号从1开始
	//将各组人数从大到小输出
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (isRoot[i] != 0) {//（各组）根节点---（各组）个数
			if (cnt == 0) {
				cnt++;
				cout << isRoot[i];//因为排序了，从大到小，所以前几个一定有值
			}
			else cout << " " << isRoot[i];
		}
	}

	for (int i = 1; i <= n; i++) {
		isRoot[findFather(i)]++;//i的根节点是findFather(i)，人数加1
	}

	int ans = 0;//组数/集合个数/根节点个数
	for (int i = 1; i <= n; i++) {
		if (isRoot[i] != 0) {
			ans++;//组数---根节点个数
		}
	}

void init(int n) {
	for (int i = 1; i <= n; i++) {
		father[i] = i;
	}
}


int findFather(int i) {//2.查找
	if (father[i] == i)return i;
	else {
		int F=findFather(father[i]);
		father[i] = F;
		return F;
	}
}

void Union(int a, int b) {/3.并
	int faA = findFather(a);
	int faB = findFather(b);
	//对于当前读入的人的编号i和他喜欢的每1个活动，合并findFather(course[h])
	if (faA != faB)father[faA] = faB;
}

//有N个人，每个人喜欢若干项活动
//如果2个人有任意1个活动相同，那么称它们处于同1个社交网络
	//若A和B属于同1个社交网络，B和C属于同1个社交网络，那么A,B,C属于同一个社交网络
//求这N个总共形成了多少社交网络

/*
8//8个人
3: 2 7 10//1号喜欢3个活动，分别是2，7，10
1 : 4//2
2 : 5 3//3
1 : 4//4
1 : 3//5
1 : 4//6
4 : 6 8 1 5//7
1 : 4//8
*/
//

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int father[1010];
int course[1010] = { 0 };//用course[h]来记录任意一个喜欢活动h的人的编号
int isRoot[1010] = { 0 };//记录每个节点是否作为某个集合的根节点


bool cmp(int a, int b) {
	return a > b;//降序//从大到小
}
void init(int n) {
	for (int i = 1; i <= n; i++) {
		father[i] = i;
	}
}


int findFather(int i) {//2.查找
	if (father[i] == i)return i;
	else {
		int F=findFather(father[i]);
		father[i] = F;
		return F;
	}
}

void Union(int a, int b) {/3.并
	int faA = findFather(a);
	int faB = findFather(b);
	//对于当前读入的人的编号i和他喜欢的每1个活动，合并findFather(course[h])
	if (faA != faB)father[faA] = faB;
}

int main() {
	int n, k, h;
	cin >> n;
	init(n);//人的编号从1开始//1.初始化
	for (int i = 1; i <= n; i++) {
		scanf_s("%d:", &k);//活动个数
		for (int j = 0; j < k; j++) {
			cin >> h;//输入第i好人喜欢的活动
			if (course[h] == 0) {//如果活动h第一次有人喜欢
				course[h] = i;//令i喜欢活动h
			}
			Union(i,findFather(course[h]));//对于当前读入的人的编号i和他喜欢的每1个活动，合并findFather(course[h])
		}
	}

	for (int i = 1; i <= n; i++) {
		isRoot[findFather(i)]++;//i的根节点是findFather(i)，人数加1
	}

	int ans = 0;//组数/集合个数/根节点个数
	for (int i = 1; i <= n; i++) {
		if (isRoot[i] != 0) {
			ans++;//组数---根节点个数
		}
	}

	cout << ans << endl;

	sort(isRoot + 1, isRoot + n + 1, cmp);//人的编号从1开始
	//将各组人数从大到小输出
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (isRoot[i] != 0) {//（各组）根节点---（各组）个数
			if (cnt == 0) {
				cnt++;
				cout << isRoot[i];//因为排序了，从大到小，所以前几个一定有值
			}
			else cout << " " << isRoot[i];
		}
	}
	return 0;
}