c++基于size和rank并查集優(yōu)化是怎樣的

這篇文章將為大家詳細(xì)講解有關(guān)c++基于size和rank并查集優(yōu)化是怎樣的，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

蟠龍ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

基于size的優(yōu)化是指：當(dāng)我們在指定由誰連接誰的時候，size數(shù)組維護(hù)的是當(dāng)前集合中元素的個數(shù)，讓數(shù)據(jù)少的指向數(shù)據(jù)多的集合中

基于rank的優(yōu)化是指：當(dāng)我們在指定由誰連接誰的時候，rank數(shù)組維護(hù)的是當(dāng)前集合中樹的高度，讓高度低的集合指向高度高的集合

運(yùn)行時間是差不多的：

基于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為根的集合中元素的個數(shù)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為根的集合的層數(shù)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

關(guān)于c++基于size和rank并查集優(yōu)化是怎樣的就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

分享題目：c++基于size和rank并查集優(yōu)化是怎樣的
鏈接URL：http://bm7419.com/article44/goeshe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、網(wǎng)站收錄、網(wǎng)站設(shè)計、網(wǎng)站改版、建站公司、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)