并查集解法

#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <algorithm>

using namespace std;

class DSU {
public:
  DSU(int n) : count_(n), p_(n + 1) {
    iota(begin(p_), end(p_), 0);
  };
  ~DSU() {};

  int Find(int x) {
    return p_[x] ^ x ? p_[x] = Find(p_[x]) : x; 
  }

  void Union(const int u, const int v) {
    if (u == v) return;
    const int pu = Find(u);
    const int pv = Find(v);
    if (pu == pv) return;
    p_[pu] = pv;
    --count_;
  }

  int get_count() const {
    return count_;
  }

private:
  int count_;
  vector<int> p_;
};

const int N = 1010, M = 1010;
int n;

int main(void) {
  scanf("%d", &n);

  DSU dsu(n);
  vector<vector<int>> hobbies(n + 1);
  unordered_map<int, vector<int>> groups;

  for (int personId = 1; personId <= n; ++personId) {
    int cnt;
    scanf("%d:", &cnt);
    while (cnt--) {
      int hobbyId;
      scanf("%d", &hobbyId);
      hobbies[personId].emplace_back(hobbyId);
      groups[hobbyId].emplace_back(personId);
    }
  }

  for (int i = 1; i <= n; ++i)
    for (int j : hobbies[i]) // 把有共同爱好的人合并在一起
      for (int k : groups[j]) dsu.Union(i, k);

  unordered_map<int, int> counts;
  for (int i = 1; i <= n; ++i)
    ++counts[dsu.Find(i)];

  vector<int> v;
  for (auto&& [id, cnt] : counts)
    v.emplace_back(cnt);

  sort(rbegin(v), rend(v));

  printf("%d\n", dsu.get_count());
  for (int i = 0; i < v.size(); ++i) {
    printf("%d", v[i]);
    if (i < v.size() - 1) printf("%s", " ");
  }
}