并查集的应用-创新互联
定义
专注于为中小企业提供成都网站建设、做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业衡阳免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了成百上千家企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
应用
若某个朋友圈过于庞大,要判断两个人是否是在一个朋友圈,确实还很不容易,给出某个朋友关系图,求任意给出的两个人是否在一个朋友圈。 规定:x和y是朋友,y和z是朋友,那么x和z在一个朋友圈。如果x,y是朋友,那么x的朋友都与y的在一个朋友圈,y的朋友也都与x在一个朋友圈。
如下图:
代码:
//找朋友圈个数 //找父亲节点 int FindRoot(int child1, int *_set) { int root = child1; while (_set[root] >= 0) { root = _set[root]; } return root; } //合并 void Union(int root1, int root2, int *&_set) { _set[root1] += _set[root2]; _set[root2] = root1; } int Friend(int n, int m, int r[][2])//n为人数,m为组数,r为关系 { assert(n > 0); assert(m > 0); assert(r); int *_set = new int[n]; for (int i = 0; i < n+1; i++) { _set[i] = -1; } for (int i = 0; i < m; i++) { int root1 = FindRoot(r[i][0],_set); int root2 = FindRoot(r[i][1],_set); if ((_set[root1] == -1 && _set[root2] == -1) || root1 != root2) { Union(root1, root2, _set); } } int count = 0; for (int i = 1; i <= n; i++) { if (_set[i] < 0) { count++; } } return count; } //主函数 #define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include #include"UnionFindSet.h" int main() { int r[][2] = { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 5, 6 } }; cout << Friend(6, 4, r) << endl; system("pause"); return 0; }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前标题:并查集的应用-创新互联
文章转载:http://pwwzsj.com/article/dgoeoo.html