L3-003 社交集群

L3-003 社交集群 (30 分)

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

输入格式：

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

$K_i: h_i[1] h_i[2] \dots h_i[K_i]$

其中$K_i(>0)$是兴趣爱好的个数，$h_i[j]$是第_j_个兴趣爱好的编号，为区间 $[1, 1000]$ 内的整数。

输出格式：

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

输入样例：

输出样例：

3
4 3 1

分析

并查集题，使用数组 table[i] 记录第 $i$ 个兴趣第一次出现的人的编号

之后每次对于已经出现过的兴趣，将出现这个兴趣的人和第一个出现这个兴趣的人进行合并

数组 num[i] 存储每个集群的人数，最后排序输出

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 1023;
int fa[MAXN], num[MAXN], table[MAXN];
int n;

void init()
{
    for(int i = 0; i < MAXN; ++i)
        fa[i] = i;
}

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

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

bool camp(int a, int b)
{
    return a > b;
}

int main()
{
    int t, tc, ans = 0;
    cin >> n;
    init();
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d:", &t);
        while(t--)
        {
            cin >> tc;
            if(!table[tc])
                table[tc] = i;
            else
                merge(table[tc], i);
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        if(fa[i] == i)  // 如果i的父亲是自己，那么就是一个集群的首领
            ans++;      // 集群数量++
        num[find(i)]++; // 在其首领处++，统计集群人数
    }
    sort(num+1, num+n+1, camp);
    cout << ans << endl;
    for(int i = 1; i <= ans; ++i)
        printf(i == ans ? "%d" : "%d ", num[i]);
    cout << endl;
    return 0;
}