PAT-A1107

#include<stdio.h> #include<algorithm> using namespace std; int hobby[1010]={0}, father[1010]={0}, num[1010]={0}; bool cmp(int a,int b){ return a>b; } int find_father(int x){ int temp=x; while(father[x]!=x){ x=father[x]; } int fathe=x;//路径压缩 x=temp; while(father[x]!=x){ temp=father[x]; father[x]=fathe; x=temp; } return fathe; } void uunion(int a, int b){ int faA=find_father(a); int faB=find_father(b); if(faA!=faB)father[faA]=faB; } int main(){ int i, j, n, k, temp, sum=0; scanf("%d",&n); for(i=1;i<=n;i++)father[i]=i; for(i=1;i<=n;i++){ scanf("%d:",&k); for(j=0;j<k;j++){ scanf("%d",&temp); if(hobby[temp]==0)hobby[temp]=i; uunion(i,find_father(hobby[temp])); } } for(i=1;i<n+1;i++){ num[find_father(i)]++; } for(i=1;i<n+1;i++){ if(num[i]!=0)sum++;; } sort(num+1,num+1+n,cmp); printf("%d\n",sum); for(i=1;i<=sum;i++){ printf("%d",num[i]); if(i<sum)printf(" "); } return 0; }