本文主要是介绍PAT 1107，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
//union findfather 通过根节点得到组数
const int maxn=1010;
int father[maxn];
vector<int> hobby[maxn];
vector<int> s;
int num[maxn]={0};
int findroot(int x)
{int a=x;while(x!=father[x])x=father[x];while(father[a]!=a){int z=a;father[a]=x;a=father[z];}return x;
}void _union(int x,int y)
{if(findroot(x)!=findroot(y))father[findroot(x)]=y;
}bool cmp(int a,int b)
{return a>b;
}
int main()
{int n,m;scanf("%d",&n);for(int i=1;i<=n;i++){father[i]=i;}int a,b;for(int i=1;i<=n;i++){scanf("%d:",&m);for(int j=1;j<=m;j++){scanf("%d",&a);hobby[a].push_back(i);}}for(int i=1;i<maxn;i++){if(hobby[i].size()!=0){for(int j=0;j<hobby[i].size()-1;j++){_union(hobby[i][j],hobby[i][j+1]);}}}int ans=0;for(int i=1;i<maxn;i++){if(father[i]==i)ans++;}for(int i=1;i<=n;i++){num[findroot(i)]++;}sort(num,num+maxn,cmp);printf("%d\n",ans);for(int i=0;i<ans;i++){printf("%d",num[i]);if(i<ans-1)printf(" ");}system("pause");return 0;
}这篇关于PAT 1107的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
