文章目錄

• 并查集的原理
• 并查集的實(shí)現(xiàn)
• 例題

---

并查集的原理

在一些應(yīng)用問題中，需要將n個(gè)不同的元素劃分成一些不相交的集合。開始時(shí)，每個(gè)元素自成一個(gè)
單元素集合，然后按一定的規(guī)律將歸于同一組元素的集合合并。在此過程中要反復(fù)用到查詢某一
個(gè)元素歸屬于那個(gè)集合的運(yùn)算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集(union-find
set)。

并查集底層通常常用數(shù)組存儲(chǔ)，并且存在以下特性：

數(shù)組的下標(biāo)對(duì)應(yīng)集合中元素的編號(hào)

數(shù)組中如果為負(fù)數(shù)，負(fù)號(hào)代表根，數(shù)字代表該集合中元素個(gè)數(shù)

數(shù)組中如果為非負(fù)數(shù)，代表該元素雙親在數(shù)組中的下標(biāo)

這里舉一個(gè)例子，假設(shè)今年秋季大一開學(xué)時(shí)班級(jí)共有10名學(xué)生，上海3人，海南4人，廣東3人。這些學(xué)生都是剛進(jìn)入校園，彼此都不認(rèn)識(shí)，一開始每一個(gè)學(xué)生都是一個(gè)獨(dú)立的小團(tuán)體，現(xiàn)在用下標(biāo)來為學(xué)生們編號(hào)，順序按照上面的所在地。

因?yàn)閬碜酝粋€(gè)地方的學(xué)生他們從小的風(fēng)俗習(xí)慣都十分接近，并且也有共同話題，所以很快他們就形成了自己的小團(tuán)體

緊接著，因?yàn)閬碜陨虾５?號(hào)同學(xué)和來自海南的5號(hào)同學(xué)是同一個(gè)宿舍的，所以他也很快融入了2號(hào)的朋友圈，并且把自己的朋友也介紹給2號(hào)，所以此時(shí)上海和海南的朋友圈集合開始交集


通過這個(gè)結(jié)構(gòu)，可以確認(rèn)此時(shí)存在著兩個(gè)集合，集合上海-海南共有7人，集合背景共有3人。

通過這種并查集的結(jié)構(gòu)，可以用來解決以下問題

查找元素屬于哪個(gè)集合

查看兩個(gè)元素是否屬于同一個(gè)集合

將兩個(gè)集合歸并成一個(gè)集合

集合的個(gè)數(shù)

---

并查集的實(shí)現(xiàn)

class UnionFindSet { public://初始化時(shí)將所有元素置為-1，表示每一個(gè)都是獨(dú)立的集合UnionFindSet(size_t size): _ufs(size, -1),_rank(size, 1){}//找到某一個(gè)集合的根int FindRoot(int index){//根節(jié)點(diǎn)的值為負(fù)數(shù)，如果不為負(fù)則說明不是根節(jié)點(diǎn)，繼續(xù)找while (_ufs[index] >= 0){//因?yàn)槊總€(gè)節(jié)點(diǎn)存儲(chǔ)自己父節(jié)點(diǎn)的下標(biāo)，所以往上繼續(xù)查找index = _ufs[index];}return index;}//將兩個(gè)集合并集bool Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);//本來就是一個(gè)集合，不需要合并if (root1 == root2){return false;}/*優(yōu)化，讓小集合掛在大集合上，減少查詢次數(shù)if (_rank[root1] < _rank[root2 ]) {swap(root1 , root2);}_rank[root1] += _rank[root2];*///選擇root1作為根，將root2所在集合合并到root1中_ufs[root1] += _ufs[root2];//將另一個(gè)的父節(jié)點(diǎn)設(shè)置為root1_ufs[root2] = root1;return true;}//求集合的個(gè)數(shù)，即負(fù)節(jié)點(diǎn)的個(gè)數(shù)size_t count() const{size_t count = 0;for (auto it : _ufs){if (it < 0){count++;}}return count;}private:std::vector<int> _ufs;std::vector<int> _rank; //用于加速查找 };

---

例題

并查集一般可以解決以下問題：

查找元素屬于哪個(gè)集合

查看兩個(gè)元素是否屬于同一個(gè)集合

將兩個(gè)集合歸并成一個(gè)集合

集合的個(gè)數(shù)

例如leetcode-547.朋友圈就屬于上面的第四種問題，也就是我最開始舉例的那個(gè)問題

class Solution { public:int findCircleNum(vector<vector<int>>& M) {UnionFindSet ufs(M.size());/*M[i][j] = x 代表著i同學(xué)和j同學(xué)之間的關(guān)系為x*/for(int i = 0; i < M.size(); i++){for(int j = 0; j < M[i].size(); j++){//如果為朋友，則將兩人并集if(M[i][j] == 1){ufs.Union(i, j);}}}return ufs.count();} };

---

leetcode-990. 等式方程的可滿足性就屬于上面的第二類問題

主要思路就是判斷不等集合是否與相等集合產(chǎn)生交集

/*思路:兩次遍歷數(shù)據(jù)，第一次將所有相等集合并集。第二次查找相等集合中是否有數(shù)據(jù)存在于不等集合，如果有則說明產(chǎn)生互斥，返回false */ class Solution { public:bool equationsPossible(vector<string>& equations) {UnionFindSet ufs(26);for(const auto& str : equations){//將相等的數(shù)據(jù)放入集合中if(str[1] == '='){ufs.Union(str[0] - 'a', str[3] - 'a');}}for(const auto& str : equations){//判斷不等的兩端是否處于集合，如果有則說明產(chǎn)生互斥，不滿足條件，返回falseif(str[1] == '!'){if(ufs.FindRoot(str[0] - 'a') == ufs.FindRoot(str[3] - 'a')){return false;}}}return true;} };

總結(jié)

以上是生活随笔為你收集整理的高级数据结构与算法 | 并查集(Union-Find)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。