PTA A_1107 Social Clusters

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805361586847744

解：
并查集

1. #include<cstdio>
   
2. #include<algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int father[1010], hobby[1010] = {0};
   
7. 
   
8. int find_root(int n)
   
9. {
   
10.     int r = n;
    
11. 
    
12.     while (r != father[r])
    
13.         r = father[r];
    
14.    
    
15.     while (n != father[n])
    
16.     {
    
17.         int z = n;
    
18.         n = father[n];
    
19.         father[z] = r;
    
20.     }
    
21. 
    
22.     return r;
    
23. }
    
24. 
    
25. void Union(int a, int b)
    
26. {
    
27.     if (find_root(a) != find_root(b)) father[father[b]] = father[a];
    
28. }
    
29. 
    
30. bool cmp(int a, int b)
    
31. {
    
32.     return a > b;
    
33. }
    
34. 
    
35. int main(void)
    
36. {
    
37.     int n;
    
38. 
    
39.     scanf("%d", &n);
    
40.     for (int i = 1; i <= n; i++)
    
41.     {
    
42.         father[i] = i;
    
43. 
    
44.         int m;
    
45.         scanf("%d:", &m);
    
46.         while (m--)
    
47.         {
    
48.             int k;
    
49.             scanf("%d", &k);
    
50. 
    
51.             if (hobby[k])
    
52.                 Union(hobby[k], i);
    
53.             else
    
54.                 hobby[k] = i;
    
55.         }
    
56.     }
    
57.    
    
58.     int cnt[1010] = {0};
    
59.     for (int i = 1; i <= n; i++)
    
60.         cnt[find_root(i)]++;
    
61. 
    
62.     sort(cnt, cnt + 1010, cmp);
    
63. 
    
64.     int k = 0;
    
65.     while (cnt[k])
    
66.         k++;
    
67. 
    
68.     printf("%d\n", k);
    
69.     for (int i = 0; i < k; i++)
    
70.     {
    
71.         printf("%d", cnt[i]);
    
72.         if (i < k - 1)  putchar(' ');
    
73.     }
    
74. 
    
75.     return 0;
    
76. }

复制代码