PAT-A 真题 – 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$ ( $\leq 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

题目大意：给出所有人的兴趣爱好（数字表示），包含任何一个相同爱好的都是一个群体，求问这里有多少个群体，并按照降序输出群体内的人数。

这是一个并查集的问题，统计人数可以使用按秩归并来统计，因为0在兴趣爱好的ID范围内，可以先将所有点初始化为0，然后用负数表示是根节点，绝对值表示这个根节点对应的树有多少个成员。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1010
int U[MAXN];

int Find(int n){    //并查集查找
  if(U[n] <= 0) return n;    //小于0，表示根节点
  else return U[n] = Find(U[n]);    //路径压缩
}

void Union(int x, int y){    //并查集联合
  x = Find(x), y = Find(y);    
  if((-U[x]) < (-U[y])){    //按秩归并，小树贴在大树上
    U[y] += U[x];    //累计人数
    U[x] = y;        //联合
  }else{
    U[x] += U[y];
    U[y] = x;
  }
}

int main(){
  fill(U, U + MAXN, 0);    //并查集初始化为0
  int N;
  cin >> N;
  for(int i = 0; i < N; i++){
    int cnt, root;    
    scanf("%d:%d", &cnt, &root);//读取个数和一个节点，这里使用第一个输入来寻根
    root = Find(root);        //寻根
    U[root]--;    //节点存放的数值--，也就是人数++
    cnt--;
    while(cnt--){
      int h;
      cin >> h;
      Union(root, h);    //联合
    }
  }
  vector<int> stu_cnt;    //存放人数的容器
  for(int i = 0; i < MAXN; i++){
    if(U[i] < 0){
      stu_cnt.push_back(U[i]);
    }
  }
  sort(stu_cnt.begin(), stu_cnt.end());    //对人的个数进行排序，因为存放的是负数，所以可以从小到大排序
  cout << stu_cnt.size() << endl;
  for(int i = 0; i < stu_cnt.size(); i++){
    cout << -stu_cnt[i];   
    if(i != stu_cnt.size()-1) cout << ' ';
  }
  return 0;
}

斐斐のBlog