【PAT A1107】Social Cluster

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

思路
从输入样例的第一个人开始，活动为2，7，10的人都可以借由1做朋友，也就是说，我们可以把2，7，10作为一个集合，不妨把每一行的第一个活动的根作为根，把后面的活动的根全都并到这个根上，并且每输入一行就把这个根的人数加一即可。（这题de了我好久bug，还是菜）

#include <cstdio>
#include <algorithm>
using namespace std;

bool cmp(int a, int b){
	return a > b;
}

int main(){
	int father[1010];//记录活动的集合关系
	int cnt[1010] = {0};//cnt[i]用于记录活动i的人数（非根为0）
	for(int i = 0; i < 1010; i++)
		father[i] = i;

	int num;
	scanf("%d", &num);
	for(int i = 0; i < num; i++){
		int numHobby, root;
		scanf("%d:", &numHobby);
		for(int j = 0; j < numHobby; j++){
			int hobby;
			scanf("%d", &hobby);
			if(j == 0){
				while(father[hobby] != hobby)
					hobby = father[hobby];
				root = hobby;
				cnt[root]++;
			}
			else{
				while(father[hobby] != hobby)
					hobby = father[hobby];
				if(hobby != root){
					cnt[root] += cnt[hobby];
					cnt[hobby] = 0;
					father[hobby] = root;
				}
			}
		}
	}
	sort(cnt, cnt + 1010, cmp);
	int total = 0;
	for(int i = 0; i < 1010; i++){
		if(cnt[i] != 0)
			total++;
		else
			break;
	}	
	printf("%d\n", total);
	for(int i = 0; i < total; i++){
		printf("%d", cnt[i]);
		if(i < total - 1)
			printf(" ");
	}
	return 0;
}