A1107. Social Clusters

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:

Sample Output:

3
4 3 1

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int cnt[1001] = {0,0}, father[1001], hobby[1001] = {0,0};
 6 int N;
 7 int findFather(int x){
 8     int a = x;
 9     while(father[x] != x){
10         x = father[x];
11     }
12     while(a != x){
13         int temp = a[father];
14         a[father] = x;
15         a = temp;
16     }
17     return x;
18 }
19 void union_(int a, int b){   //a集合的根节点不变
20     int tempa = findFather(a);
21     int tempb = findFather(b);
22     if(tempa != tempb){
23         father[tempb] = a;
24     }
25 }
26 bool cmp(int a, int b){
27     return a > b;
28 }
29 int main(){
30     int N;
31     scanf("%d", &N);
32     for(int i = 1; i <= N; i++){
33         father[i] = i;
34     }
35     for(int i = 1; i <= N; i++){
36         int num, temp;
37         scanf("%d:", &num);
38         for(int j = 0; j < num; j++){
39             scanf("%d", &temp);
40             if(hobby[temp] == 0){
41                 hobby[temp] = i;
42             }else{
43                 union_(hobby[temp], i);
44             }
45         }
46     }
47     for(int i = 1; i <= N; i++){
48         int root = findFather(i);
49         cnt[root]++;
50     }
51     int ans = 0;
52     for(int i = 1; i <= N; i++){
53         if(cnt[i] != 0)
54             ans++;
55     }
56     sort(cnt, cnt + N + 1, cmp);
57     printf("%d
%d", ans, cnt[0]);
58     int k = 1;
59     while(k < N && cnt[k] != 0){
60         printf(" %d", cnt[k]);
61         k++;
62     }
63     cin >> N;
64     return 0;
65 }

View Code

总结：

1、题意：看了书上的解释才搞明白这道题什么意思。并不是说一个set里的所有人都要有共同的hobby，而是当两个人有至少一个共同hobby时，他们就处于一个set。比如A的hobby是1、2，B的hobby是2、3，则AB在一个set中。而C的hobby是3、4，则B、C在一个set中。AB同set，BC同set，则ABC同属一个set。其实就是考并查集。

2、并查集的要点：

father[a] = b，表示a的父节点是b。若father[i] = i，则i是根节点。 初始化时，每个节点都初始化为根节点。
查找根节点：当x != father[x] 时，不断进行x = father[x] 的操作即可。
合并：为防止出现环路，只能对不同的集合做合并。所以合并a、b时，先找到a的根节点roota， b的根节点rootb，如果roota ！= rootb，则 father[rootb] = roota。严格按这个流程做可以避免出错。不要仅仅把b的父亲设为roota。
路径压缩：为了降低查找的复杂度。可以放在查找根节点的函数中，当找到 x 的根节点 root 时，再从 x 往根节点回溯一次，沿途所有节点的父节点均设置为 root。

3、只有两个人有共同hobby才将他们所在的两个set做合并，但如果对每个人保存一个hobby列表，然后每两个人检查是否有共同爱好会很费时。可以设置一个hobby数组，hobby[i]仅仅记录一个人，就是首个读入的有这个爱好的人，并将这个人作为他所在set的root节点一直不变。