这篇文章将为大家详细讲解有关c++基于size和rank并查集优化是怎样的，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
创新互联建站专业为企业提供
陇川网站建设、陇川做网站、陇川网站设计、陇川网站制作等企业网站建设、网页设计与制作、陇川企业网站模板建站服务，十载
陇川做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
基于size的优化是指：当我们在指定由谁连接谁的时候，size数组维护的是当前集合中元素的个数，让数据少的指向数据多的集合中
基于rank的优化是指：当我们在指定由谁连接谁的时候，rank数组维护的是当前集合中树的高度，让高度低的集合指向高度高的集合
运行时间是差不多的：
基于size的代码： UnionFind3.h
#ifndef UNION_FIND3_H_#define UNION_FIND3_H_#include#includenamespace UF3{class UnionFind{private:int* parent;int* sz; //sz[i]就表示以i为根的集合中元素的个数int count;public:UnionFind(int count){this->count = count;parent = new int[count]; sz = new int[count];for(int i = 0 ; i < count ; i++){parent[i] = i;sz[i] = 1;}}~UnionFind(){delete [] parent;delete [] sz;}int find(int p){assert(p < count && p >= 0); while( p != parent[p]) //这个是写到find里面的{p = parent[p];}return p;}void unionElements(int p , int q){int pRoot = find(p);int qRoot = find(q);if( pRoot == qRoot)return;if(sz[pRoot] < sz[qRoot]){parent[pRoot] = qRoot;sz[qRoot] += sz[pRoot];}else{parent[qRoot] = pRoot;sz[pRoot] += sz[qRoot];}}bool isConnected(int p , int q){return find(p) == find(q);}};};#endif
基于rank的代码： UnionFind4.h
#ifndef UNION_FIND4_H_#define UNION_FIND4_H_#include#includenamespace UF4{class UnionFind{private:int* parent;int* rank; //rank[i]就表示以i为根的集合的层数int count;public:UnionFind(int count){this->count = count;parent = new int[count]; rank = new int[count];for(int i = 0 ; i < count ; i++){parent[i] = i;rank[i] = 1;}}~UnionFind(){delete [] parent;delete [] rank;}int find(int p){assert(p < count && p >= 0); while( p != parent[p]) //这个是写到find里面的{p = parent[p];}return p;}void unionElements(int p , int q){int pRoot = find(p);int qRoot = find(q);if( pRoot == qRoot)return;if(rank[pRoot] < rank[qRoot]){parent[pRoot] = qRoot;}else if( rank[pRoot] > rank[qRoot] ){parent[qRoot] = pRoot;}else{parent[pRoot] = qRoot; //这里谁指向谁无所谓rank[qRoot] ++;}}bool isConnected(int p , int q){return find(p) == find(q);}};};#endif
关于c++基于size和rank并查集优化是怎样的就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
文章标题：c++基于size和rank并查集优化是怎样的-创新互联
分享URL：
http://cdxtjz.cn/article/dshcjc.html
