1107 Social Clusters （并查集）

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h> // 以防万一，使用scanf时加上这个头文件 
using namespace std;
int n;
vector<int>father,isRoot;
int course[1001] = {0};//vector可以实现动态设置数组大小，但是效率比数组低
int FindFather(int x){
	int a = x;
	while(x != father[x]){
		x = father[x];
	}
	while(a != father[a]){ //路径压缩
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}
void Union(int a,int b){
	int fa = FindFather(a);
	int fb = FindFather(b);
	if(fa != fb)  father[fa] = fb;
}
bool cmp(int &a,int &b){
	return a>b;
}
int main()
{
	cin>>n;
	father.resize(n+1),isRoot.resize(n+1);
	for(int i=1;i<=n;i++)father[i] = i;
	for(int i=1;i<=n;i++){
		int k ;
		scanf("%d:",&k);
		for(int j =0;j<k;j++){
			int t;
			cin>>t;
			if(0 == course[t])
			course[t] = i;
			Union(i,FindFather(course[t]));
		} 
	}
	for(int i=1;i<=n;i++){
		isRoot[FindFather(i)]++;
	}
	sort(isRoot.begin(),isRoot.end(),cmp);
	int cnt=0;
	while(isRoot[cnt++]);//下表从零开始，cnt最后的值会比非零的下标大2
	printf("%d
",cnt-1);
	for(int i=0;i<cnt-1;i++){
		printf("%d",isRoot[i]);
		if(i !=cnt-2) printf(" ");//printf("%d%s",isRoot[i],i == cnt-2?"":" ")三目运算符的效率比较低，在汇编的时候比对应的if-else多一条指令
	} 
	return 0;
}