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:
Ki: hi[1] hi[2] … hi[Ki]
where Ki (>0) is the number of hobbies, and hi[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:
|
1 2 3 4 5 6 7 8 9 |
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:
|
1 2 |
3 4 3 1 |
用 Disjoint Sets 解决……
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<stdio.h> #include<stdlib.h> #include<memory.h> int set_find(int *set,int index) { int temp,root; temp=index; while(set[temp]>=0) { temp=set[temp]; } root=temp; temp=index; while(set[temp]>=0) { index=temp; temp=set[temp]; set[index]=root; } return root; } int set_union(int *set,int a,int b) { a=set_find(set,a); b=set_find(set,b); if(a==b) { return 0; } if(set[a]<set[b]) { set[a]+=set[b]; set[b]=a; } else { set[b]+=set[a]; set[a]=b; } return 0; } int compare(const void *a,const void *b) { return *(int *)a-*(int *)b; } int main() { int n,i,j,k,*clusters,index,hobby[1001]; scanf("%d",&n); clusters=(int *)malloc(n*sizeof(int)); memset(clusters,0xFF,n*sizeof(int)); memset(hobby,0xFF,1001*sizeof(int)); for(i=0;i<n;i++) { scanf("%d:",&k); for(j=0;j<k;j++) { scanf("%d",&index); if(hobby[index]==-1) { hobby[index]=i; } else { set_union(clusters,i,hobby[index]); } } } qsort(clusters,n,sizeof(int),compare); for(i=0;i<n;i++) { if(clusters[i]>=0) { break; } } n=i; printf("%d\n",n); if(n>0) { printf("%d",-clusters[0]); for(i=1;i<n;i++) { printf(" %d",-clusters[i]); } } } |