PTA A_1107 Social Clusters

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805361586847744

解：
并查集

#include<cstdio>
#include<algorithm>

using namespace std;

int father[1010], hobby[1010] = {0};

int find_root(int n)
{
    int r = n;

    while (r != father[r])
        r = father[r];
    
    while (n != father[n])
    {
        int z = n;
        n = father[n];
        father[z] = r;
    }

    return r;
}

void Union(int a, int b)
{
    if (find_root(a) != find_root(b)) father[father[b]] = father[a];
}

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

int main(void)
{
    int n;

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        father[i] = i;

        int m;
        scanf("%d:", &m);
        while (m--)
        {
            int k;
            scanf("%d", &k);

            if (hobby[k]) 
                Union(hobby[k], i);
            else 
                hobby[k] = i;
        }
    }
    
    int cnt[1010] = {0};
    for (int i = 1; i <= n; i++)
        cnt[find_root(i)]++; 

    sort(cnt, cnt + 1010, cmp);

    int k = 0;
    while (cnt[k])
        k++;

    printf("%d\n", k);
    for (int i = 0; i < k; i++)
    {
        printf("%d", cnt[i]);
        if (i < k - 1)  putchar(' ');
    }

    return 0;
}