1107 Social Clusters （30 分)

2019-04-22

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:

1
2

3
4 3 1

作者: CHEN, Yue

单位: 浙江大学

时间限制: 1200 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出N个学生和他们的兴趣，要求根据共同兴趣划分小圈子。输出小圈子个数和各圈子人数。

分析

刷了一百多题了，好像是PAT第一次出现并查集。实现findfather和makeunion操作。然后用hobby[t]数组记录第一个兴趣为t的人。之后每次遇到t，将当前的人合并到第一兴趣为t的人的集合即可。

然后遍历每个人，计算他们的father并用map统计人数。再把人数放入vector中排序输出即可。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
int n;
int hobby[1001];
int father[100010];
int findfather(int i){
    int x=i;
    while(father[x]!=x)
        x=father[x];
    int temp;
    //降低深度
    while(father[i]!=x){
        temp=father[i];
        father[i]=x;
        i=temp;
    }
    return x;
}

void makeunion(int a,int b){
    int xa=findfather(a);
    int xb=findfather(b);
    if(xa!=xb)
        father[xb]=xa;
}
int main() {
    int c,t;
    cin>>n;
    for(int i=1;i<=n;i++) {
        father[i]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d:",&c);
        for(int j=0;j<c;j++){
            cin>>t;
            if(hobby[t]==0)
                hobby[t]=i;
            makeunion(i,findfather(hobby[t]));
        }
    }

    map <int,int> mapp;
    for(int i=1;i<=n;i++)
        mapp[findfather(i)]++;
    vector<int> count;
    for(auto it:mapp)
        count.push_back(it.second);
    sort(count.rbegin(),count.rend());
    cout<<count.size()<<endl;
    int f=0;
    for(int i=0;i<count.size();i++){
        f++==0?cout<<"":cout<<" ";
        cout<<count[i];
    }
    return 0;
}