PAT A1107 Social Clusters （30 分）—

PAT A1107 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

where

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:

Sample Output:

3
4 3 1

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <set>
 4 #include <string.h>
 5 #include <vector>
 6 #include <math.h>
 7 #include <queue>
 8 using namespace std;
 9 const int maxn = 1011;
10 int n;
11 int father[maxn]={0};
12 int peo[maxn][maxn];
13 set<int> hob;
14 set<int> fah;
15 int res[maxn]={0};
16 bool cmp(int a,int b){
17     return a>b;
18 }
19 void init(){
20     for(int i=1;i<=maxn;i++){
21         father[i]=i;
22     }
23 }
24 int findfather(int x){
25     int a=x;
26     while(x!=father[x]){
27         x=father[x];
28     }
29     while(a!=father[a]){
30         int z=a;
31         a=father[a];
32         father[z]=x;
33     }
34     return x;
35 }
36 void uni(int a,int b){
37     int fa=findfather(a);
38     int fb = findfather(b);
39     if(fa!=fb){
40         father[fb]=fa;
41     }
42 }
43 int main(){
44     init();
45     scanf("%d",&n);
46     for(int i=1;i<=n;i++){
47         int k,fi;
48         scanf("%d: %d",&k,&fi);
49         peo[i][0]=fi;
50         hob.insert(fi);
51         for(int j=1;j<k;j++){
52             int x;
53             scanf("%d",&x);
54             peo[i][j]=x;
55             hob.insert(x);
56             uni(fi,x);
57         }
58     }
59     for(auto it:hob){
60         fah.insert(findfather(it));
61         //printf("%d %d
",it,findfather(it));
62     }
63     printf("%d
",fah.size());
64     for(int i=1;i<=n;i++){
65         res[findfather(peo[i][0])]++;
66         //printf("%d %d
",findfather(peo[i][0]),res[findfather(peo[i][0])]);
67     }
68     sort(res,res+maxn,cmp);
69     for(int i=0;i<fah.size();i++){
70         printf("%d",res[i]);
71         if(i<fah.size()-1)printf(" ");
72     }
73 }

View Code

注意点：标准并查集，我是根据喜好来把人集合起来的，变量有点多，有点麻烦。看了大佬的代码，发现好像所有并查集的题目都是可以套模板的，他们是合并人，标记爱好，然后遍历isroot来得到集合个数

---------------- 坚持每天学习一点点