L3-003 社交集群

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

输入格式：

输入在第一行给出一个正整数 \(N\)（ \(≤1000\) ），为社交网络平台注册的所有用户的人数。于是这些人从 \(1\) 到 \(N\) 编号。随后 \(N\) 行，每行按以下格式给出一个人的兴趣爱好列表：

\(K_{i}\) : \(h_{i}[1]\) \(h_{i}[2]\) ... \(h_{i}[K_{i}]\)

其中 \(K_{i}\) ( \(>0\) )是兴趣爱好的个数，\(h_{i}[j]\) 是第 \(j\) 个兴趣爱好的编号，为区间 \([1, 1000]\) 内的整数。

输出格式：

首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

输入样例：

输出样例：

3
4 3 1

解题思路

这道题算是L3中比较简单的一道题。题目所说的具有相同爱好的人都放到一起，其实可以把具有相同爱好这一点理解成两个人之间存在联系，并且这个联系是可以相互传递的，加入把相同爱好的人看作是朋友的话，那么我朋友的朋友也是我的朋友，题目的大致意思就是要将所有存在联系的朋友都放入到一个集合中，并且统计每个集合中的人数。朋友的朋友也是我的朋友，这显然就是一个并查集的问题，不过这道题由于编号并不连续，所以不能单纯的取维护并查集的大小，而需要在建立完并查集之后，在统计每个首领下的人数。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
//typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

const int N = 1010;
int fa[N], cnt[N], a[N], n;

int find(int x){
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}

void Union(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    fa[fx] = fy;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    for(int i = 1; i < N; i ++ ) fa[i] = i;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ){
        int k, x; scanf("%d: %d", &k, &x);
        a[i] = x, k -- ;
        while(k -- ){
            int y; scanf("%d", &y);
            Union(x, y);
        }
    }

    for(int i = 1; i <= n; i ++ ){
        int x = find(a[i]);
        cnt[x] ++ ;
    }

    vector<int> res;
    for(int i = 1; i < N; i ++ )
        if(cnt[i]) res.push_back(cnt[i]);
    
    sort(res.begin(), res.end(), [](int &a, int &b){
        return a > b;
    });

    cout << (int)res.size() << endl;
    for(int i = 0; i < (int)res.size() - 1; i ++ ) printf("%d ", res[i]);
    printf("%d\n", res.back());

    return 0;
}