﻿ PAT-1107 Social Clusters (30 分)

### PAT-1107 Social Clusters (30 分)

```8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4```

```3
4 3 1```

``` 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