PAT甲级1107并查集

经典并查集，参加蓝桥杯的都做烂了hhhhh

v [ i ] 指向父节点，num [ i ] 记录喜欢这个hobby的人数（因为一个人算一次所以就加第一次）

路径压缩这么写比较方便：（因为find ( v [ x ] ) 返回的是v[x]=x 的终点情况，所以每一个路径上的节点都指向这个终点。）

int find(int x){ if(v[x]!=x) v[x]=find(v[x]); return v[x]; }

接着就遍历一遍v [ i ] ，如果不是终点（v [ i ] != i）就把该点的人数 num [ i ] 传递给num [ v[ i ] ]

最后就是把 数组num 排序找到人数不是 0 的节点就可以啦~ 

#include<iostream> using namespace std; char s; int v[1050]={0},num[1050]={0},ans,n,k,temp,first; int find(int x){ if(v[x]!=x) v[x]=find(v[x]); return v[x]; } void merge(int a,int b){ a=find(a);b=find(b); v[b]=a; } bool cmp(int a,int b){ return a>b; } int main(){ cin>>n; for(int i=0;i<=1000;i++)v[i]=i; for(int i=0;i<n;i++){ cin>>k>>s>>first; for(int j=1;j<k;j++){ cin>>temp; merge(first,temp); } num[v[first]]++; } for(int i=0;i<=1000;i++){ if(v[i]!=i){ num[v[i]]+=num[i]; num[i]=0; } } sort(num,num+1001,cmp); for(int i=0;i<=1000;i++)if(num[i]!=0)ans++; cout<<ans<<endl; for(int i=0;i<ans;i++){ if(i)cout<<" "; cout<<num[i]; } return 0; }