本文主要是介绍GPLT社交集群，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
团体程序设计天梯赛-练习集
L3-003 社交集群 (30分)
当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。
输入格式：
输入在第一行给出一个正整数 N（≤1000），为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行，每行按以下格式给出一个人的兴趣爱好列表：
K**i: h**i[1] h**i[2] … h**i[K**i]
其中K**i(>0)是兴趣爱好的个数，h**i[j]是第j个兴趣爱好的编号，为区间 [1, 1000] 内的整数。
输出格式：
首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。
输入样例：
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
输出样例：
3
4 3 1
思路：并查集，把有相同兴趣爱好的人并在一起即可。当然并在一起的人只需要有至少一个相同的兴趣就好了。
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>using namespace std;
const int N = 2e3 + 10;
int fa[N];int find(int x)
{while(x != fa[x])x = fa[x] = find(fa[x]);return x;
}void Union(int u, int v)
{int fu = find(u);int fv = find(v);if(fu != fv)fa[fu] = fv;
}int main()
{int n;scanf("%d", &n);vector<vector<int> >v(n+1);for(int i = 1; i <= n; i++){int num;scanf("%d:", &num);v[i].resize(num+1);//第i个人有num个兴趣，存放在[1,num]中for(int j = 1; j <= num; j++){int number;scanf("%d", &number);v[i][j] = number;}}for(int i = 1; i <= n; i++)fa[i] = i;for(int i = 1; i <= n; i++){//i,j分别表示俩个人,k,l枚举俩个人的所有爱好for(int j = 1; j <= n; j++){for(int k = 1; k < v[i].size(); k++){for(int l = 1; l < v[j].size(); l++){//第i个人和第j个人不分在同一组，但是他们有相同的兴趣爱好if(find(i) != find(j) && v[i][k] == v[j][l]){Union(i, j);}}}}}vector<int>a;for(int i = 1; i <= n; i++){if(find(i) == i){//数一下当前集合共有多少人int tot = 0;for(int j = 1; j <= n; j++){if(find(j) == i)tot++;}a.push_back(tot);}}printf("%d\n", a.size());sort(a.begin(), a.end(), greater<int>());//对集合人数排降序for(int i = 0; i < a.size(); i++){if(i!=0)printf(" ");printf("%d", a[i]);}return 0;
}
/*
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
*/这篇关于GPLT社交集群的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
