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

并查集的基本应用，有几个地方是模版务必记一下

  1. find_father()函数
  2. Union()函数
  3. 初始化函数init（）也可以直接写在主函数里
  4. 50到58行的代码

代码

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. using namespace std;
  6. const int maxn = 1010;
  7. int m, n;
  8. int father[maxn];
  9. int is_root[maxn] = {0};
  10. int course[maxn];
  12. int find_father(int i){
  13.     if(father[i] == i) return i;
  14.     else{
  15.         int f = find_father(father[i]);
  16.         father[i] = f;
  17.         return f;
  18.     }
  19. }
  21. void Union(int a, int b){
  22.     int faA = find_father(a);
  23.     int faB = find_father(b);
  24.     if(faA!=faB) father[faA] = faB;
  25. }
  27. void init(){
  28.     for(int i = 1; i <= n; i++){
  29.         father[i] = i;
  30.         is_root[i] = false;
  31.     }
  32. }
  34. bool cmp(int a, int b){
  35.     return a > b;
  36. } 
  38. int main(){
  39.     int  temp; 
  40.     scanf("%d", &n);
  41.     init();
  42.     for(int i = 1; i <= n; i++){
  43.         scanf("%d:", &m);
  44.         for(int j = 0; j < m; j++){
  45.             scanf("%d", &temp);
  46.             if(course[temp] == 0) course[temp] = i;
  47.             Union(i, find_father(course[temp]));
  48.         }
  49.     }
  50.     for(int i = 1; i <= n; i++){
  51.         is_root[find_father(i)]++;
  52.     }
  53.     int count = 0;
  54.     for(int i = 1; i <= n; i++){
  55.         if(is_root[i] != 0){
  56.             count++; 
  57.         }
  58.     }
  59.     printf("%d\n", count);
  60.     sort(is_root + 1, is_root + n + 1, cmp);
  61.     for(int i = 1; i <= count; i++){
  62.         printf("%d", is_root[i]);
  63.         if(i != count) printf(" ");
  64.     }
  65.     return 0;
  66. }