L3-003 社交集群

并查集的应用，我感觉这题不是很容易想出来。然后....代码看注释吧。
写法一，

#include <bits/stdc++.h>
using namespace std;
int a[1010][1010],fa[1010];
int getf(int x){
	while(fa[x]!=-1){
		x=fa[x];
	}
	return x;
}
void merge(int x,int y){
	int f1 =getf(x);
	int f2 =getf(y);
	if(f1==f2) return;
	fa[f1]=f2;
}
int main(){
    int n;
    cin>>n;
    memset(fa,-1,sizeof(fa));
    for(int i=1;i<=n;i++){//第i个人 
    	int count;
    	cin>>count;
    	cin.get();
        while(count--){
        	int tno;
        	cin>>tno;//兴趣编号
			for(int j=1;j<i;j++){//遍历之前的人 
				if(a[j][tno]){
					merge(i,j);
				}
			} 
            a[i][tno]=1;
		}
	}
	map<int,int> mp;//集群的根，集群里面的人数 
	for(int i=1;i<=n;i++){
		int root =getf(i);
		mp[root]++;
	}
	vector<int> res;
	for(auto x : mp){
		res.push_back(x.second);//人数排序 
	}
	sort(res.begin(),res.end(),greater<int>());
	int flag = 0;
	cout << res.size() << '\n';
	for(int i=0;i<res.size();i++){
		if(flag) cout<<" ";
		cout<<res[i];
		flag++;
	}
	return 0;
}

写法二，

#include <bits/stdc++.h>
using namespace std;
int record[1010],fa[1010];//record[i]为兴趣爱好编号为i的人 
int getf(int x){
	while(fa[x]!=-1){
		x=fa[x];
	}
	return x;
}
void merge(int x,int y){
	int f1 =getf(x);
	int f2 =getf(y);
	if(f1==f2) return;
	fa[f1]=f2;
}
int main(){
	memset(fa,-1,sizeof(fa));
	int n;
	cin>>n;
    for(int i=1;i<=n;i++){//第i个人 
    	int count;
    	cin>>count;
    	cin.get();
    	while(count--){
    		int tno;
    		cin>>tno;
    		if(record[tno]){
    			merge(i,record[tno]);
		    }else{
		    	record[tno]=i;
			}
		}
	}
	map<int,int> mp;//集群的根，集群里面的人数 
	for(int i=1;i<=n;i++){
		int root =getf(i);
		mp[root]++;
	}
	vector<int> res;
	for(auto x : mp){
		res.push_back(x.second);//人数排序 
	}
	sort(res.begin(),res.end(),greater<int>());
	int flag = 0;
	cout << res.size() << '\n';
	for(int i=0;i<res.size();i++){
		if(flag) cout<<" ";
		cout<<res[i];
		flag++;
	}
	return 0;
}