【C++高階數(shù)據(jù)結(jié)構(gòu)】并查集-創(chuàng)新互聯(lián)

🏆個人主頁：企鵝不叫的博客
創(chuàng)新互聯(lián)建站專業(yè)為企業(yè)提供城子河網(wǎng)站建設(shè)、城子河做網(wǎng)站、城子河網(wǎng)站設(shè)計(jì)、城子河網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、城子河企業(yè)網(wǎng)站模板建站服務(wù)，十年城子河做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
? 🌈專欄
C語言初階和進(jìn)階
C項(xiàng)目
Leetcode刷題
初階數(shù)據(jù)結(jié)構(gòu)與算法
C++初階和進(jìn)階
《深入理解計(jì)算機(jī)操作系統(tǒng)》
《高質(zhì)量C/C++編程》
Linux
?? 博主碼云gitee鏈接：代碼倉庫地址
?若有幫助可以【關(guān)注+點(diǎn)贊+收藏】，大家一起進(jìn)步！

💙系列文章💙

文章目錄

💙系列文章💙
💎一、概念
💎二、實(shí)現(xiàn)
- 🏆1.框架
- 🏆2.查找元素屬于哪個集合
- - 壓縮路徑
- 🏆3.合并兩個集合
- 🏆4.判斷兩個元素是否在同一個集合當(dāng)中
- 🏆5.統(tǒng)計(jì)集合個數(shù)
💎三、練習(xí)
- 🏆1.劍指 Offer II 116. 省份數(shù)量
- 🏆2.990. 等式方程的可滿足性

💎一、概念

并查集是多個獨(dú)立集合的合集，用于表示數(shù)據(jù)之間的關(guān)系，并查集中的每一個集合是用多叉樹來表示的。

舉例：現(xiàn)在有十個元素，每個元素的值都初始化為-1
現(xiàn)在將0，3，4這三個元素構(gòu)成一個集合，我們讓0為根，將根放到3和4下標(biāo)對應(yīng)的元素上，同時(shí)將3和4原本對應(yīng)的元素加給0下標(biāo)對應(yīng)的元素
同理將2，5，7，8和1，6，9構(gòu)成一個集合，默認(rèn)2和1為根
同理將0集合和1集合合并，默認(rèn)0是根

總結(jié)：
數(shù)組的下標(biāo)對應(yīng)集合中元素的編號
數(shù)組中如果為負(fù)數(shù)，負(fù)號代表根，數(shù)字的絕對值代表該集合中元素個數(shù)
數(shù)組中如果為非負(fù)數(shù)，代表該元素雙親在數(shù)組中的下標(biāo)

💎二、實(shí)現(xiàn) 🏆1.框架

底層使用vector實(shí)現(xiàn)，并且全部初始化為-1
class UnionFindSet {public:
	UnionFindSet(int sz)
		:_ufs(sz, -1) {}
private:
	vector_ufs;
};

🏆2.查找元素屬于哪個集合

當(dāng)元素對應(yīng)的下標(biāo)對應(yīng)的內(nèi)容為正數(shù)時(shí)（也就是該元素不為根），我們需要更新該下標(biāo)，也就是index=_ufs[index]，讓自己成為雙親
繼續(xù)判斷，如果對應(yīng)內(nèi)容為負(fù)數(shù)，說明該下標(biāo)是根，直接返回
int FindRoot(int x){while (_ufs[x] >= 0) {//更新親人
        x = _ufs[x];
    }
    return x;
}

壓縮路徑

并查集的訪問是依靠數(shù)組下標(biāo)實(shí)現(xiàn)的隨機(jī)訪問，時(shí)間復(fù)雜度為O(1)，只有數(shù)據(jù)樣本量極大的時(shí)候，可以考慮路勁壓縮
//查找元素屬于哪個集合
	int FindRoot(int x){int root = x;
		while (_ufs[root] >= 0) {	//更新親人
			root = _ufs[root];
		}
		//壓縮路徑
		while (_ufs[x] >0) {	int parent = _ufs[x];
			_ufs[x] = root;
			x = parent; 
		}
		return root;
	}

🏆3.合并兩個集合

找到兩個集合對應(yīng)的根
如果兩個根相等說明兩個集合相等，如果兩個根不相等則讓其中一個根歸并到一個根的下面，更新新的雙親的內(nèi)容和被并入的根的內(nèi)容
void Union(int x, int y) {int root1 = FindRoot(x);
    int root2 = FindRoot(y);
    if (root1 != root2) {_ufs[root1] += _ufs[root2];
        _ufs[root2] = root1;
    }
}

🏆4.判斷兩個元素是否在同一個集合當(dāng)中

如果兩個集合根相等說明在同一個集合當(dāng)中
bool isUnion(int x, int y) {return FindRoot(x) == FindRoot(y);
	}

🏆5.統(tǒng)計(jì)集合個數(shù)

遍歷一遍數(shù)組，統(tǒng)計(jì)內(nèi)容為負(fù)數(shù)的下標(biāo)的個數(shù)，即統(tǒng)計(jì)了集合個數(shù)
int size() {int count = 0;
		for (auto e : _ufs) {	if (e< 0) {		++count;
			}
		}
		return count;
	}

💎三、練習(xí) 🏆1.劍指 Offer II 116. 省份數(shù)量

傳送門

在這里插入圖片描述

思路：遍歷所有元素，將相關(guān)聯(lián)的數(shù)放到同一個集合當(dāng)中，最后統(tǒng)計(jì)集合數(shù)量即可

class Solution {public:
 int FindRoot(const vector& v, int x){ while(v[x] >0){ x = v[x];
     }
     return x;
 }
 int findCircleNum(vector>& isConnected) { vectorv(isConnected.size(), -1);
     for(int i = 0; i< isConnected.size(); ++i){ for(int j = 0; j< isConnected[0].size(); ++j){ if(isConnected[i][j] == 1){//1表示該元素在同一個元素中
                 int root1 = FindRoot(v, i);
                 int root2 = FindRoot(v, j);
                 if(root1!=root2){ v[root1] += v[root2];
                     v[root2] = root1;
                 }
             }
         }
     }
     int count = 0;
     for(auto e : v){ if(e< 0){ ++count;
         }
     }
     return count;
 }
};

🏆2.990. 等式方程的可滿足性

傳送門

在這里插入圖片描述

思路：如果兩個字符相等，則放入同一個集合之中。
如果兩個字符不相等，它們應(yīng)當(dāng)在不同的集合中，此時(shí)查找它們所在集合的根，如果相同則說明這兩個字符在同一個集合中，返回false。

class Solution {public:
int FindRoot(const vector& v, int x){while(v[x] >= 0){  x = v[x];
  }
  return x;
}
bool equationsPossible(vector& equations){vectorv(26, -1);
//第一遍遍歷，將相同的值放到同一個集合當(dāng)中
for(auto& e : equations){if(e[1] == '='){  int root1 = FindRoot(v, e[0]-'a');
      int root2 = FindRoot(v, e[3]-'a');
      if(root1 != root2){  v[root1]+=v[root2];
          v[root2] = root1;
      }
  }
}
//第二遍遍歷，講不同的值比較，如果相同說明悖論了，返回false
for(auto& e : equations){if(e[1] == '!'){  int root1 = FindRoot(v, e[0]-'a');
      int root2 = FindRoot(v, e[3]-'a');
      if(root1 == root2){  return false;
      }
  }
}
return true;
}
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：【C++高階數(shù)據(jù)結(jié)構(gòu)】并查集-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://muchs.cn/article12/deojgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、網(wǎng)站內(nèi)鏈、動態(tài)網(wǎng)站、商城網(wǎng)站、網(wǎng)站維護(hù)、搜索引擎優(yōu)化

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

猜你還喜歡下面的內(nèi)容