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:
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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int cnt[] = {,}, father[], hobby[] = {,};
int N;
int findFather(int x){
int a = x;
while(father[x] != x){
x = father[x];
}
while(a != x){
int temp = a[father];
a[father] = x;
a = temp;
}
return x;
}
void union_(int a, int b){ //a集合的根节点不变
int tempa = findFather(a);
int tempb = findFather(b);
if(tempa != tempb){
father[tempb] = a;
}
}
bool cmp(int a, int b){
return a > b;
}
int main(){
int N;
scanf("%d", &N);
for(int i = ; i <= N; i++){
father[i] = i;
}
for(int i = ; i <= N; i++){
int num, temp;
scanf("%d:", &num);
for(int j = ; j < num; j++){
scanf("%d", &temp);
if(hobby[temp] == ){
hobby[temp] = i;
}else{
union_(hobby[temp], i);
}
}
}
for(int i = ; i <= N; i++){
int root = findFather(i);
cnt[root]++;
}
int ans = ;
for(int i = ; i <= N; i++){
if(cnt[i] != )
ans++;
}
sort(cnt, cnt + N + , cmp);
printf("%d\n%d", ans, cnt[]);
int k = ;
while(k < N && cnt[k] != ){
printf(" %d", cnt[k]);
k++;
}
cin >> N;
return ;
}
总结：
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节点一直不变。