PAT1107 甲级
代码如下
#include&nbsp;<iostream>
#include&nbsp;<algorithm>
using&nbsp;namespace&nbsp;std;
int&nbsp;father[1001];
int&nbsp;hobby[1001]={0};
int&nbsp;cnt[1001]={0};
bool&nbsp;compare(int&nbsp;a,int&nbsp;b)
{
return&nbsp;a>b;
}
int&nbsp;findfather(int&nbsp;x)
{
int&nbsp;v;
if(x==father[x]){return&nbsp;x;}
else{
v=findfather(father[x]);
father[x]=v;
return&nbsp;v;
}
}
void&nbsp;unionset(int&nbsp;a,int&nbsp;b)
{
int&nbsp;fathera=findfather(a);
int&nbsp;fatherb=findfather(b);
if(fathera&nbsp;!=&nbsp;fatherb)
{
father[fatherb]=fathera;
}
}
int&nbsp;main()
{
int&nbsp;numpeople;
int&nbsp;eachnum;
for(int&nbsp;p=0;p<1001;p++)
{
father[p]=p;
}
int&nbsp;index;
scanf("%d",&numpeople);
for(int&nbsp;i=1;i<=numpeople;i++)
{
scanf("%d:",&eachnum);
for(int&nbsp;j=0;j<eachnum;j++)
{
cin>>index;
if(hobby[index]==0)
{
hobby[index]=i;
}
unionset(i,hobby[index]);
}
}
for(int&nbsp;i=1;i<=numpeople;i++)
{
cnt[findfather(i)]++;
}
int&nbsp;count=0;
for(int&nbsp;i=0;i<1001;i++)
{
if(cnt[i]!=0)
{
count++;
}
}
sort(cnt,cnt+1001,compare);
cout<<count<<endl;
for(int&nbsp;q=0;q<count-1;q++)
{
cout<<cnt[q]<<"&nbsp;";
}
cout<<cnt[count-1];
return&nbsp;0;
}