1107 social clusters (30 points)

maxmin

1107 Social Clusters (30 branch )

The question

give n Personal interests , People with the same interests become a collection .
Number of output groups , Output the number of people in each group in descending order .

Ideas

Check your hobbies and , Open an array to record the number of people in each hobby . Finally, the number of all hobbies of a group is concentrated on the hobbies of the root node .

Code

// Begin to use map Storage , But found map It's not easy to use here , Something's wrong bug, On that basis .
#include<stdio.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
map<int,int>gp,pr;
map<int,int>::iterator itor;
map<int,int>::reverse_iterator to;
int pre[100007],ans[100007],ang[100007];
int find(int x)
{
    
	int y=x,z;
	while(x!=pre[x]){
    
		x=pre[x];
	}
	while(y!=x){
    
		z=pre[y];
		pre[y]=x;
		y=z;
	}
	return x;
}
void link(int a,int b)
{
    
	pre[a]=b;
}
bool cmp(int a,int b)
{
    
	return a>b;
}
int main()
{
    
	int n,k,x,temp,p,q,cnt=0;
	string str;
	scanf("%d",&n);
	for(int i=0;i<100007;i++){
    
		pre[i]=i;
		ans[i]=0;
	}
	for(int i=0;i<n;i++){
    
		scanf("%d",&k);
		cin>>str;
		if(k!=0){
    
			scanf("%d",&x);
			p=find(x);
			ans[p]+=1;
			gp[p]=ans[p];
			for(int j=1;j<k;j++){
    
				scanf("%d",&x);
				q=find(x);
				if(p!=q){
    
					link(q,p);
					ans[p]+=ans[q];
					gp[p]=ans[p];
					ans[q]=0;
					gp[q]=0;
				}
			}
		}
	}
	for(itor=gp.begin();itor!=gp.end();itor++){
    		// Want to use map Automatic sorting of 
// printf("!!!!%d %d\n",itor->first,itor->second);
		if(itor->second!=0){
    
// printf("@@%d \n",itor->first); 
// pr[itor->second]=itor->first;// When the two groups have the same number of people, there is a mistake here 
			ang[cnt++]=itor->second;
		}
	}
// printf("%d\n",pr.size());
	sort(ang,ang+cnt,cmp);
	printf("%d\n",cnt);
	for(int i=0;i<cnt;i++){
    
		if(i!=0){
    
			printf(" ");
		}
		printf("%d",ang[i]);
	}
// for(to=pr.rbegin();to!=pr.rend();to++){
    
// if(to!=pr.rbegin()){
    
// printf(" ");
// }
// cout<<to->first<<" "<<to->second<<endl;;
// }
	return 0;
}