798236606 发表于 2020-2-15 11:24:47

PTA A_1107 Social Clusters

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

解：
并查集
#include<cstdio>
#include<algorithm>

using namespace std;

int father, hobby = {0};

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

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

    return r;
}

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

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;

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

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

    sort(cnt, cnt + 1010, cmp);

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

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

    return 0;
}
页: [1]
查看完整版本: PTA A_1107 Social Clusters