pat-a 1107. Social Clusters (30)

并查集，我写的多了一点。

简单说下就行，两个人如果有共同的爱好就是一个圈子里面的。开始错误原因在于压缩路径不够彻底。因为最后判断有几个圈子时没有去寻找根直接判断父节点，因此要压缩到底才能直接判断。

#include<cstdio> #include<algorithm> #include<functional> using namespace std; int num[1010][1010]; int p[1010]; int visit[1010]; void init(){ for(int i=0;i<1010;++i) p[i]=i; } int find(int x){ if(p[x]==x) return x; else return p[x]=find(p[x]); } void merge(int i,int j){ int x=find(i); int y=find(j); if(x!=y){ if(x>y) p[x]=y; else p[y]=x; } } int main(){ int n,t,a,ans=0,flag=0,k=0; int c[1010]; scanf("%d",&n); init(); for(int i=0;i<n;++i){ scanf("%d:",&t); while(t--){ scanf("%d",&a); num[i][a]=1; for(int j=0;j<i;++j){ if(num[j][a]){ merge(i,j); } } } } for(int i=0;i<n;++i){ for(int j=0;j<i;++j){ if(find(i)==find(j)) merge(i,j); } } //for(int i=0;i<n;++i) printf("%d ",p[i]); for(int i=0;i<n;++i){ visit[p[i]]++; if(visit[p[i]]==1) ans++; } printf("%d\n",ans); for(int i=0;i<n;++i){ if(visit[i]){ c[k++]=visit[i]; } } sort(c,c+k,greater<int>()); for(int i=0;i<k;++i){ if(flag)printf(" %d",c[i]); else{ flag=1; printf("%d",c[i]); } } return 0; }

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A "social cluster" is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (<=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

K_i: h_i[1] h_i[2] ... h_i[K_i]

where K_i (>0) is the number of hobbies, and h_i[j] is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input: 8 3: 2 7 10 1: 4 2: 5 3 1: 4 1: 3 1: 4 4: 6 8 1 5 1: 4 Sample Output: 3 4 3 1