PAT-1107 Social Clusters (30 分)

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805361586847744

3
4 3 1

题解：把每个爱好的合并在一起，每个集合的father节点计数--->总的圈子数以及圈子里的人数，

 1 #include <string.h>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <math.h>
 5 #include <iostream>
 6 using namespace std;
 7 const int maxn=1000+5;
 8 int father[maxn], hobby[maxn]={0}, isRoot[maxn]={0};
 9 
10 void init(int n){
11     for(int i=1;i<=n;i++) father[i]=i,isRoot[i]=0;
12 }
13 
14 int find(int x){
15     int a=x;
16     while(x!=father[x]){
17         x=father[x];
18     }
19     while(a!=father[a]){ //路径压缩 
20         int z=a;
21         a=father[a];
22         father[z]=x;
23     }
24     return x;
25 }
26 
27 void Union(int u, int v){
28     int a=find(u);
29     int b=find(v);
30     if(a!=b){
31         father[a]=b;
32     }
33 }
34 
35 bool cmp(int x, int y){
36     return x>y;
37 }
38 
39 
40 int main(){
41     int n,k,h;
42     scanf("%d",&n);
43     init(n);
44     for(int i=1;i<=n;i++) {
45         scanf("%d:",&k);
46         for (int j=0;j<k;j++){
47             scanf("%d",&h);
48             if(hobby[h]==0) hobby[h]=i;
49             Union(i, hobby[h]);
50         }
51     }
52     for(int i=1;i<=n;i++)
53         isRoot[find(i)]++;
54     int ans=0;
55     for(int i=1;i<=n;i++)
56         if(isRoot[i])
57             ans++;
58     printf("%d
",ans);
59     sort(isRoot+1, isRoot+1+n,cmp);
60     for(int i=1;i<=ans;i++){
61         printf("%d",isRoot[i]);
62         if(i<ans) printf(" ");
63     }
64     return 0;
65     
66 }

菠萝的版本

 1 def person_hobby2():
 2     n=int(input())
 3     hobby_person={}
 4     for i in range(n):
 5         person_hobby=set(map(int,input().split()[1:]))
 6         temp=[]
 7         for j,k in hobby_person.items():
 8             if not person_hobby.isdisjoint(k[0]):
 9                 temp.append(j)
10         hobby_person[i]=[person_hobby,1]
11         for j in temp:
12             hobby_person[i][0].update(hobby_person[j][0])
13             hobby_person[i][1]+=hobby_person[j][1]
14             del hobby_person[j]
15     print(len(hobby_person))
16     ans=[]
17     for i in hobby_person.values():
18         ans.append(i[1])
19     print(' '.join(map(str,sorted(ans,reverse=True))))    
20 
21 if __name__ == "__main__":
22     person_hobby2()

View Code