题目粗心:
有N集体,如果任意2集体的喜好有雷同的(就是有交加),那么这2集体就是属于同一个社交网络,要求输入这N集体组成了几个社交网络,并且输入每个社交网络的人数
算法思路:
此题考查的是并查集的应用(并查集次要用来解决 若干个节点,有些节点相互相连,有些节点没有连贯,如何判断其中两个节点是否相连这样的问题),目前来看,应用并查集求解此题应该是最好的抉择,能够应用构建人与人的关系图,而后遍历有多少个连通重量,每一个连通重量有多少节点,然而这种形式实现起来过于简单。
并查集次要由1个汇合,2个操作所组成,汇合就是father保留每一个节点的父节点,2个操作别离是查问节点x的父亲节点和合并2个节点所在的汇合。入上面代码所示:
int father[1005];// 每一个节点的父亲节点// 查问节点x的父亲节点int findFather(int x){ while(x!=father[x]){ x = father[x]; } return x;//father[x]==x的才是根节点}// 合并a和b节点所在的汇合void Union(int a,int b){ int fa = findFather(a); int fb = findFather(b); if(fa!=fb){ father[fa] = fb; }}
在此题中,咱们须要构建一个人与人之间互相关联的社交网络,媒介是每一个人所领有的喜好,那么咱们应用$hobbyOwner$记录每一个喜好的所有者,这样在输出每一个喜好的时候,如果以后喜好没有所有者,将以后喜好标记为本人所独有,否则就将该喜好所有者和以后人合并到一个社交网络。在每一个社交网络构建实现后,咱们须要统计社交网络的个数和每一个社交网络的人数,咱们应用$roots(set汇合)$保留每一个社交网络的根节点,其个数即为社交网络的个数,$cluster$保留每一个社交网络的人数,具体做法就是,须要遍历每一个人,找到其根节点$root$,而后增加进$roots$中,并且统计以后社交网络的人数++cluster[root]
。最初对cluster进行排序输入即可。
int cluster[1005];// 每一个社交网络的人数unordered_set<int> roots;// 保留每一个根节点// 统计社交网络的个数,也就是根节点的个数for (int k = 1; k <= N; ++k) { int root = findFather(k); ++cluster[root]; roots.insert(root);}
留神点:
- 1、有一种状况须要特地留神,如果当初曾经组建好了社交网络A和B,那么当初有一个人的喜好既有A又有B,那么他将作为连贯A和B的桥梁,须要将每一个人的所有喜好都要进行解决,并且因为合并后,只更新了一个社交网络的根节点的父亲,该社交网络的其余节点的父亲仍然没有变动,所以在统计社交网络的人数的时候不能间接应用father数组,肯定得从新遍历每一个节点获取其父亲,否则测试点1,4,5会谬误。
提交后果:
AC代码:
#include <cstdio>#include <unordered_map>#include <unordered_set>#include <algorithm>using namespace std;int father[1005];// 每一个节点的父亲节点unordered_map<int,int> hobbyOwner;//每一个喜好的所有者int cluster[1005];// 每一个社交网络的人数// 初始化每一个节点的父亲void init(){ for (int i = 1; i <= 1000; ++i) { father[i] = i; }}// 查问节点x的父亲节点int findFather(int x){ while(x!=father[x]){ x = father[x]; } return x;//father[x]==x的才是根节点}// 合并a和b节点所在的汇合void Union(int a,int b){ int fa = findFather(a); int fb = findFather(b); if(fa!=fb){ father[fa] = fb; }}bool cmp(int a,int b){ return a>b;}int main(){ init(); int N;// 节点个数 scanf("%d",&N); for (int i = 1; i <= N; ++i) { int K; scanf("%d: ",&K); for (int j = 0; j < K; ++j) { int hobby; scanf("%d",&hobby); if(hobbyOwner[hobby]==0){ // 以后喜好没有人领有 hobbyOwner[hobby] = i; } else { // 曾经领有了,合并拥有者和i Union(hobbyOwner[hobby],i); } } } unordered_set<int> roots;// 保留每一个根节点 // 统计社交网络的个数,也就是根节点的个数 for (int k = 1; k <= N; ++k) { int root = findFather(k); ++cluster[root]; roots.insert(root); } printf("%lu\n",roots.size()); sort(cluster+1,cluster+N+1,cmp); for(int i=1;i<=roots.size();++i){ printf("%d",cluster[i]); if(i<roots.size()) printf(" "); } return 0;}