慈溪专业做网站公司,40平小商铺装修,环评在那个网站做,免费公司介绍网站怎么做当你在社交网络平台注册时#xff0c;一般总是被要求填写你的个人兴趣爱好#xff0c;以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。
输入格式
输入在第一行给出一个正整数 N#xff08;≤1000一般总是被要求填写你的个人兴趣爱好以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。
输入格式
输入在第一行给出一个正整数 N≤1000为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行每行按以下格式给出一个人的兴趣爱好列表 K i : h i [ 1 ] h i [ 2 ] . . . h i [ K i ] K_i: h_{i}[1]\ h_{i}[2]\ ...\ h_{i}[K_i] Ki:hi[1] hi[2] ... hi[Ki]其中 K i ( 0 ) K_i(0) Ki(0) 是第 i 个人的兴趣爱好的个数 h i [ j ] h_{i}[j] hi[j]是第 j 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一些限制
项目限制代码长度限制16 KB时间限制3000 ms内存限制64 MB栈限制8192 KB
解题思路
因为每一个人的兴趣爱好不止一个如果我们按照单一的兴趣爱好来合并那就会非常不妥当当然这样做也是可以通过的但所花的时间会更多。
我们可以这样做
先设置一个映射关系unordered_mapint, vectorint将每个人归入到每个兴趣爱好的集合中。遍历这个映射关系对于每一个兴趣爱好的集合将这个集合中的人合并到一个朋友圈中。for(auto k: lov) {for(int i 0, j 1; j k.second.size(); j) {union1(k.second[i], k.second[j]);}
}最后使用set容器来存储所有的朋友圈使用unordered_map来存储每个朋友圈的人数最后输出结果。setint components;
unordered_mapint, int mp;
for(int i 1; i n; i) {components.insert(components.end(), fa[i]);if(mp.find(fa[i]) mp.end()) mp[fa[i]] 1;else mp[fa[i]] 1;
}
cout components.size() endl;
vectorint ans;
for(auto i: mp) {ans.push_back(i.second);
}Code
#include bits/stdc.h
using namespace std;
int fa[2000];
setint components;
unordered_mapint,vectorint lov;void init(int n) {for(int i 1; i n; i) {fa[i] i;}
}int find(int i) {if(i fa[i]) return i;else {fa[i] find(fa[i]);return fa[i];}
}int update(int i) {if(i fa[i]) return i;else {fa[i] find(fa[i]);return fa[i];}
}void union1(int a, int b) {int afa find(a), bfa find(b);fa[afa] bfa;
}bool cmp(int a, int b) {return a b;
}int main() {int n, m, t;cin n;init(n);for(int i 1; i n; i) {scanf(%d: , m);for(int j 1; j m; j) {scanf(%d, t);lov[t].push_back(i);}}for(auto k: lov) {for(int i 0, j 1; j k.second.size(); j) {union1(k.second[i], k.second[j]);}}for(int i 0; i n; i) {update(i);}unordered_mapint, int mp;for(int i 1; i n; i) {components.insert(components.end(), fa[i]);if(mp.find(fa[i]) mp.end()) mp[fa[i]] 1;else mp[fa[i]] 1;}cout components.size() endl;vectorint ans;for(auto i: mp) {ans.push_back(i.second);}sort(ans.begin(), ans.end(), cmp);for(int i 0; i ans.size(); i) {if(i 0) cout ans[i];else cout ans[i];}
}
