PAT-A 1107 Social Clusters（30 分）并查集入门

https://pintia.cn/problem-sets/994805342720868352/problems/994805361586847744

1107 Social Clusters（30 分）

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

K​i​​: h​i​​[1] h​i​​[2] ... h​i​​[K​i​​]

where K​i​​ (>0) is the number of hobbies, and h​i​​[j] is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

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

思路及关键点：

1、isRoot[i]数组表示；以i为根的集合内的元素个数（就是每个连通块集合有多少个点元素）

     isRoot采用hashtable的方式记录：

		for(int i=1;i<=n;i++){
			isRoot[findFather(i)]++;//记录每个集合内的元素个数 
		}

2、题目理解：本题中，判断两个人属于同一个社交网络的条件是：A和B有公共喜欢的活动。

最后让分别求出：连通块的数目；已经每个连通块内的元素个数；

3、样例解释：

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; 
const int nmax=1010;
int father[nmax];
int isRoot[nmax];//记录每个节点是否作为某个集合的根节点 
int course[nmax];//course[ac]表示：活动ac被主人i喜欢 

bool cmp(int a,int b){
	return a>b; 
}
int findFather(int u){
	if(u==father[u]) return u;
	else{
		int f=findFather(father[u]);
		father[u]=f;
		return f;
	}
}

void Union(int u,int v){
	int fu=findFather(u);
	int fv=findFather(v);
	if(fu!=fv){
		father[fu]=fv;
	}
}

void init(int n){
	for(int i=1;i<=n;i++){
		father[i]=i;
		isRoot[i]=0;
	}
}
int main(int argc, char** argv) {
	int n;//人数，图的点数
	while(cin>>n){
		memset(father,0,sizeof(father));
		memset(isRoot,0,sizeof(isRoot));
		memset(course,0,sizeof(course));
		init(n);
		int k;//每个人喜欢的k个活动 
		int ac;//喜欢的活动编号 
		for(int i=1;i<=n;i++){//遍历n个人 
			//cin>>k;
			scanf("%d:",&k);
			for(int j=0;j<k;j++){
				cin>>ac;
				if(course[ac]==0){//如果活动ac还没有人喜欢 
					course[ac]=i; //活动ac被主人i喜欢 
				} 
				//Union(i,father[course[h]]); 
				Union(i,findFather(course[ac]));
			} 
		}
		for(int i=1;i<=n;i++){
			isRoot[findFather(i)]++;//记录每个集合内的元素个数 
		}
		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);
		for(int i=1;i<=ans;i++){
			cout<<isRoot[i];
			if(i!=ans){
				cout<<" ";
			} 
		}
	} 
	return 0;
}