1107 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:

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

题目大意：有n个人，每个人喜欢k个活动，如果两个人有任意一个活动相同，就称为他们处于同一个社交网络。求这n个人一共形成了多少个社交网络

心得：本题是对n个人划分网络，因此并查集的范围应当选择人而不是活动，从而能够更加方便地求出每个社交网络中的人数。

代码：（优化前）

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
int father[1005], hobby[1005], clunum[1005]={0};
bool flag[1005];
using namespace std;
int findFather(int x){
    while(x != father[x]){
        x = father[x];
    }
    return x;
}
void Union(int x, int y){
    int faX = findFather(x);
    int faY = findFather(y);
    if(faX != faY){
        father[faX] = faY;
    }
}
int main(){
    int n, mx = -1;
    for(int i = 1; i <=1000; i++){
        father[i] = i;
    }
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        string Num;
        cin>>Num;
        int num = Num[0] - '0';
        int pre;
        for(int j = 0; j < num; j++){
            int index;
            cin>>index;
            if(j == 0) hobby[i] = index;
            flag[index] = 1;
            if(j != 0){
                 Union(index, pre);
            }
            pre = index;
        }
    }
    int ans = 0;
    vector<int> cluster;
    for(int i = 1; i <= 1000; i++){
        if(father[i] == i && flag[i] == 1){
            ans++;
            cluster.push_back(i);
        }
    }
    cout<<ans<<endl;
    int w = 0;
    for(int i = cluster.size() - 1; i >= 0; i--){
        int sum = 0;
        for(int j = 1; j <= n; j++){
            int faJ = findFather(hobby[j]);
            if(faJ == cluster[i]){
                sum++;
            }
        }
        clunum[w++] = sum;
    }
    sort(clunum, clunum + w, greater<int>() );
    for(int i = 0; i < w; i++){
        if(i > 0) printf(" ");
        printf("%d", clunum[i]);
    }
    return 0;
}

代码：（优化后）

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> father, isRoot;
int cmp1(int a, int b){
    return a > b;
}
int findFather(int x){
    while(x != father[x]){
        x = father[x];
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB)
        father[faA] = faB;
}
int main() {
    int n, k, t, cnt = 0;
    int course[1001] = {0};
    scanf("%d", &n);
    father.resize(n + 1);
    isRoot.resize(n + 1);
    for(int i = 1; i <= n; i++)
        father[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &t);
            if(course[t] == 0)
                course[t] = i;
            Union(i, findFather(course[t]));
        }
    }
    for(int i = 1; i <= n; i++)
        isRoot[findFather(i)]++;
    for(int i = 1; i <= n; i++) {
        if(isRoot[i] != 0)
            cnt++;
    }
    printf("%d\n", cnt);
    sort(isRoot.begin(), isRoot.end(), cmp1);
    for(int i = 0; i < cnt; i++) {
        printf("%d", isRoot[i]);
        if(i != cnt - 1) printf(" ");
    }
    return 0;
}