L3-003 社交集群

题目链接

L3-003 社交集群

分析

并查集题，使用数组 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;
}