Shulou(Shulou.com)06/03 Report--

This article will explain in detail about C++ based on size and rank and search optimization is how, the content of the article is of high quality, so the editor to share with you to do a reference, I hope you have a certain understanding of the relevant knowledge after reading this article.

Size-based optimization means that when we specify who is connected to whom, the size array maintains the number of elements in the current set, so that less data points to the collection with more data.

Rank-based optimization means that when we specify who is connected to whom, the rank array maintains the height of the tree in the current set, so that the set with low height points to the set with high height.

The running time is about the same:

Size-based code: UnionFind3.h

# ifndef UNION_FIND3_H_#define UNION_FIND3_H_#include#includenamespace UF3 {class UnionFind {private:int* parent;int* sz; / / sz [I] indicates the number of elements in the set rooted at 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]) / / this is written to 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]) / / this is written to 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[qRoot]){parent[pRoot] = qRoot;}else if( rank[pRoot] >

Rank [qRoot]) {parent [qRoot] = pRoot;} else {parent [pRoot] = qRoot; / / it doesn't matter who points to who here [qRoot] +;}} bool isConnected (int p, int Q) {return find (p) = = find (Q);};}; # endif

About C++ based on size and rank and search set optimization is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.