社交集群(并查集)

题目链接：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] 内的整数。

输出格式：

首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

水题，当时脑子短路了，想的有点复杂，要懂得转化问题，和统计集群数以及集群内数量的方法

#include
using namespace std;const int N = 1010;
int fa[N];
int ha[N];int fin(int x)
{if(x == fa[x])return x;return fa[x] = fin(fa[x]);
}bool cmp(int a,int b)
{return a > b;
}int main()
{int n,x,y;char z;cin >> n;for(int i = 0; i <= 1006; i++){fa[i] = i;ha[i] = -1;}for(int i = 1; i <= n; i++){scanf("%d",&x);cin >> z;while(x--){cin >> y;if(ha[y] == -1) ha[y] = i;else{int p = fin(i);int q = fin(ha[y]);if(p != q){fa[p] = q;}}}}int ans[N],top = 0;memset(ans,0,sizeof(ans));for(int i = 1; i <= n; i++){int p = fin(i);if(p == i){top++;}ans[p]++;}cout << top << endl;sort(ans,ans+1005,cmp);for(int i = 0; i < top-1; i++){cout << ans[i] << ' ';}cout << ans[top-1] << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！