c++并查集优化(基于size和rank)

基于size的优化是指:当我们在指定由谁连接谁的时候,size数组维护的是当前集合中元素的个数,让数据少的指向数据多的集合中

基于rank的优化是指:当我们在指定由谁连接谁的时候,rank数组维护的是当前集合中树的高度,让高度低的集合指向高度高的集合

运行时间是差不多的:

基于size的代码: UnionFind3.h

#ifndef UNION_FIND3_H_
#define UNION_FIND3_H_

#include<iostream>
#include<cassert>

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<iostream>
#include<cassert>

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++并查集亲戚(Relations)算法实例
  • c++初级并查集知识点总结
  • C++实现并查集
  • C++利用map实现并查集
  • C++并查集常用操作
  • C++并查集算法简单详解
  • C++高级数据结构之并查集

转载请注明出处:http://www.xhjyjj.com/article/20230526/171724.html