从品牌网站建设到网络营销策划,从策略到执行的一站式服务
假如已知有n个人和m对好友关系(存于数组r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈。请写程序求出这n个人里一共有多少个朋友圈。
在湟源等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站建设、成都网站设计 网站设计制作按需求定制开发,公司网站建设,企业网站建设,成都品牌网站建设,营销型网站建设,外贸营销网站建设,湟源网站建设费用合理。
例如:n=5,m=3,r={{1,2},{2,3},{4,5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于同一个朋友圈,4、5属于另一个朋友圈。结果为2个朋友圈。
这个问题可以通过数据结构中的并查集来实现。
并查集
将N个不同的元素分成一组不相交的集合。
开始时,每个元素就是一个集合,然后按规律将两个集合合并。
代码如下:
UnionFindSet.h:
#pragma once class UnionFindSet { public: UnionFindSet(int N) :_a(new int[N]) ,_n(N) { memset(_a, -1, N * 4);//将每一组初始的元素值设为-1 } //找该元素的根 int FindRoot(int x) { while (_a[x] >= 0) { x = _a[x]; } return x; } //合并 void Union(int x1, int x2) { int root1 = FindRoot(x1); int root2 = FindRoot(x2); _a[root1] += _a[root2];//将元素2的根合并到元素1的根上 _a[root2] = root1;//元素2的值设置为元素1 } //合并后集合总数 int Count() { int count = 0; for (size_t i = 0; i < _n; ++i) { if (_a[i] < 0) { ++count; } } return count; } protected: int* _a;//元素集合 size_t _n;//元素个数 };
Test.cpp
#includeusing namespace std; #include "UnionFindSet.h" int GroupsOfFriends(int n, int m, int r[][2]) { UnionFindSet ufs(n+1); for (size_t i = 0; i < m; ++i) { int x1 = r[i][0]; int x2 = r[i][1]; ufs.Union(x1, x2); } return ufs.Count()-1;//元素集合从0开始,应减去0的集合 } void Test() { int r[][2] = {{1,2}, {1,3}, {4,5}}; int count = GroupsOfFriends(5, 3, r); cout< 过程:
本文名称:C++实现并查集
网站URL:http://www.cdkjz.cn/article/pedjpo.html
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图