基于size的优化是指：当我们在指定由谁连接谁的时候，size数组维护的是当前集合中元素的个数，让数据少的指向数据多的集合中
基于rank的优化是指：当我们在指定由谁连接谁的时候，rank数组维护的是当前集合中树的高度，让高度低的集合指向高度高的集合
运行时间是差不多的：
基于size的代码： UnionFind3.h
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#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
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#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文件在上一个并查集的博客中有，就不再粘贴出来了
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_37414405/article/details/89469735
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。