小编给大家分享一下c++并查集优化的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
在新北等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站设计、
网站建设 网站设计制作
定制网站建设,公司网站建设,企业网站建设,
品牌网站建设,
成都营销网站建设,
成都外贸网站建设,新北网站建设费用合理。
基于size的优化是指：当我们在指定由谁连接谁的时候，size数组维护的是当前集合中元素的个数，让数据少的指向数据多的集合中
基于rank的优化是指：当我们在指定由谁连接谁的时候，rank数组维护的是当前集合中树的高度，让高度低的集合指向高度高的集合
运行时间是差不多的：
基于size的代码： UnionFind3.h
#ifndef UNION_FIND3_H_
#define UNION_FIND3_H_
#include
#include
namespace 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
#include
namespace 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
剩下的头文件和main文件在上一个并查集的博客中有，就不再粘贴出来了
以上是“c++并查集优化的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联网站建设公司行业资讯频道！
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
分享标题：c++并查集优化的示例分析-创新互联
标题路径：
http://cdkjz.cn/article/jdihd.html
