pat 团体天梯 L3-003. 社交集群

L3-003. 社交集群

时间限制

1000 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。

输入格式：

输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好：

K_i: h_i[1] h_i[2] ... h_i[K_i]

其中K_i（>0）是第i个人的兴趣的数量，h_i[j]是第i个人的第j项兴趣的编号，编号范围为[1, 1000]内的整数。

输出格式：

首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

输出样例：

3
4 3 1

思路：并查集，两个人若有相同的兴趣，则在一个集合中。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define N_MAX 1000+2
#define INF 0x3f3f3f3f
int n;
bool interest[N_MAX][N_MAX];
vector<int>vec[N_MAX];
int root[N_MAX];
int statistic[N_MAX];

int par[N_MAX], Rank[N_MAX];
void init(int n) {
  for (int i = 0; i < n;i++) {
    par[i] = i;
    Rank[i] = 0;
  }
}
int find(int x) {
  if (x == par[x])return x;
  else {
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y) {
  x = find(x);
  y = find(y);
  if (x == y)return;
  else {
    if (Rank[y] > Rank[x])par[x] = y;
    else {
      par[y] = x;
      if (Rank[x] == Rank[y])Rank[x]++;
    }
  }
}

bool same(int x,int y) {
  return find(x) == find(y);
}

bool cmp (const int &a,const int &b) {
  return a > b;
}

int main() {
  while (scanf("%d", &n) != EOF) {
    memset(interest,0,sizeof(interest));
    init(N_MAX);
    for (int i = 0; i < n;i++) {
      int num; scanf("%d",&num);
      scanf(": ");
      while (num--) {
        int a; scanf("%d", &a);
        interest[i][a] = true;
        vec[i].push_back(a);
      }
    }
    for (int i = 0; i < n;i++) {
      for (int j = i+1; j < n;j++) {
        for (int k = 0; k < vec[j].size();k++) {
          if (interest[i][vec[j][k]]) {
            unite(i, j); break;
          }
        }
      }
    }
    set<int>S; memset(statistic,0,sizeof(statistic));
    for (int i = 0; i < n;i++) {
      root[i] = find(i);
      S.insert(root[i]);
      statistic[root[i]]++;
    }
    printf("%d
",S.size());
    sort(statistic, statistic + n,cmp);
    for (int i = 0; i < S.size();i++) {
      printf("%d%c",statistic[i],i+1==S.size()?'
':' ');
    }
  }
  return 0;
}