pta l3-3（社交集群）

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805053141925888

题意：给定n个人，以及每个人的兴趣，把有相同兴趣的人并成一个社交集群，问有多少个群，并以非递增方式输出所有群的人数。

思路：如果合并人的话，会复杂许多，这里我们可以合并兴趣，并用每个人的第一个兴趣表示其兴趣，将每个人的所有兴趣合并起来，之后遍历n个人，要统计人的群和群的人数，与将其第一兴趣的祖先所在的群的操作一致。说的有点绕，直接看代码吧，模拟模拟就懂了。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int n,k,q,root[maxn],res[maxn],a[maxn];

 bool cmp(int x,int y){

     return x>y;

 }

 int getr(int kk){

     if(root[kk]==kk) return kk;

     else return root[kk]=getr(root[kk]);

 }

 void Union(int x,int y){

     int xr=getr(x),yr=getr(y);

     if(xr!=yr)

         root[yr]=xr;

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=;++i)

         root[i]=i;

     for(int i=;i<=n;++i){

         int t;

         scanf("%d",&k);

         getchar();

         scanf("%d",&t);

         a[i]=t,--k;

         while(k--){

             scanf("%d",&t);

             Union(a[i],t);

         }

     }

     for(int i=;i<=n;++i)

         ++res[getr(a[i])];

     for(int i=;i<=;++i)

         if(res[i]) ++q;

     sort(res,res+maxn,cmp);

     printf("%d\n",q);

     printf("%d",res[]);

     for(int i=;i<q;++i)

         printf(" %d",res[i]);

     printf("\n");

     return ;

 }

巴特西

pta l3-3（社交集群）

最新文章

热门文章