目錄本節(jié)目標(biāo)1. 并查集原理2. 并查集實(shí)現(xiàn)3. 并查集應(yīng)用省份數(shù)量等式方程的可滿足性本節(jié)目標(biāo)并查集原理并查集實(shí)現(xiàn)并查集應(yīng)用1. 并查集原理在一些應(yīng)用問題中需要將n個不同的元素劃分成一些不相交的集合。開始時每個元素自成一個單元素集合然后按一定的規(guī)律將歸于同一組元素的集合合并。在此過程中要反復(fù)用到查詢某一個元素歸屬于哪個集合的運(yùn)算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集union-find set。比如某公司今年校招全國總共招生 10 人西安招 4 人成都招 3 人武漢招 3 人10 個人來自不同的學(xué)校起先互不相識每個學(xué)生都是一個獨(dú)立的小團(tuán)體現(xiàn)給這些學(xué)生進(jìn)行編號{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}給以下數(shù)組用來存儲該小集體數(shù)組中的數(shù)字代表該小集體中具有成員的個數(shù)。負(fù)號下文解釋畢業(yè)后學(xué)生們要去公司上班每個地方的學(xué)生自發(fā)組織成小分隊(duì)一起上路于是西安學(xué)生小分隊(duì)s1{0,6,7,8}成都學(xué)生小分隊(duì)s2{1,4,9}武漢學(xué)生小分隊(duì)s3{2,3,5}就相互認(rèn)識了10 個人形成了三個小團(tuán)體。假設(shè)由三個群主 0、1、2 擔(dān)任隊(duì)長負(fù)責(zé)大家的出行。一趟火車之旅后每個小分隊(duì)成員就互相熟悉成為了一個朋友圈。從上圖可以看出編號 6、7、8 同學(xué)屬于 0 號小分隊(duì)該小分隊(duì)中有 4 人包含隊(duì)長 0編號為 4 和 9 的同學(xué)屬于 1 號小分隊(duì)該小分隊(duì)有 3 人包含隊(duì)長 1編號為 3 和 5 的同學(xué)屬于 2 號小分隊(duì)該小分隊(duì)有 3 個人包含隊(duì)長 2。仔細(xì)觀察數(shù)組中的內(nèi)容變化可以得出以下結(jié)論數(shù)組的下標(biāo)對應(yīng)集合中元素的編號數(shù)組中如果為負(fù)數(shù)負(fù)號代表根數(shù)字代表該集合中元素個數(shù)數(shù)組中如果為非負(fù)數(shù)代表該元素雙親在數(shù)組中的下標(biāo)在公司工作一段時間后西安小分隊(duì)中 8 號同學(xué)與成都小分隊(duì) 1 號同學(xué)奇跡般地走到了一起兩個小圈子的學(xué)生相互介紹最后成為了一個小圈子現(xiàn)在 0 集合有 7 個人2 集合有 3 個人總共兩個朋友圈。通過以上例子可知并查集一般可以解決以下問題查找元素屬于哪個集合沿著數(shù)組表示的樹形關(guān)系一直找到根即樹中元素為負(fù)數(shù)的位置。查看兩個元素是否屬于同一個集合沿著數(shù)組表示的樹形關(guān)系往上一直找到樹的根如果根相同表明在同一個集合否則不在。將兩個集合歸并成一個集合將兩個集合中的元素合并。將一個集合名稱改成另一個集合的名稱。集合的個數(shù)遍歷數(shù)組數(shù)組中元素為負(fù)數(shù)的個數(shù)即為集合的個數(shù)。2. 并查集實(shí)現(xiàn)classUnionFindSet{public:// 初始時將數(shù)組中元素全部設(shè)置為-1UnionFindSet(size_t size):_ufs(size,-1){}// 給一個元素的編號找到該元素所在集合的名稱intFindRoot(intindex){// 如果數(shù)組中存儲的是負(fù)數(shù)找到否則一直繼續(xù)while(_ufs[index]0){index_ufs[index];}returnindex;}boolUnion(intx1,intx2){introot1FindRoot(x1);introot2FindRoot(x2);// x1已經(jīng)與x2在同一個集合if(root1root2)returnfalse;// 將兩個集合中元素合并_ufs[root1]_ufs[root2];// 將其中一個集合名稱改變成另外一個_ufs[root2]root1;returntrue;}// 數(shù)組中負(fù)數(shù)的個數(shù)即為集合的個數(shù)size_tCount()const{size_t count0;for(autoe:_ufs){if(e0)count;}returncount;}private:vectorint_ufs;};3. 并查集應(yīng)用LCR 116. 省份數(shù)量classSolution{public:intfindCircleNum(vectorvectorintisConnected){// 手動控制并查集vectorintufs(isConnected.size(),-1);// 查找根autofindRoot[ufs](intx){while(ufs[x]0)xufs[x];returnx;};for(size_t i0;iisConnected.size();i){for(size_t j0;jisConnected[i].size();j){if(isConnected[i][j]1){// 合并集合introot1findRoot(i);introot2findRoot(j);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}}}intn0;for(autoe:ufs){if(e0)n;}returnn;}};990. 等式方程的可滿足性/* 解題思路 1. 將所有兩端的字符合并到一個集合中 2. 檢測!兩端的字符是否在同一個集合中如果在則不滿足如果不在則滿足 */classSolution{public:boolequationsPossible(vectorstringequations){vectorintufs(26,-1);autofindRoot[ufs](intx){while(ufs[x]0)xufs[x];returnx;};// 第一遍先把相等的值加到一個集合中for(autostr:equations){if(str[1]){introot1findRoot(str[0]-a);introot2findRoot(str[3]-a);if(root1!root2){ufs[root1]ufs[root2];ufs[root2]root1;}}}// 第二遍先檢查不相等的字符是否在一個集合中在一起就相悖了// 返回falsefor(autostr:equations){if(str[1]!){introot1findRoot(str[0]-a);introot2findRoot(str[3]-a);if(root1root2){returnfalse;}}}returntrue;}};