目錄本節(jié)目標1. 并查集原理2. 并查集實現(xiàn)3. 并查集應用省份數(shù)量等式方程的可滿足性本節(jié)目標并查集原理并查集實現(xiàn)并查集應用1. 并查集原理在一些應用問題中需要將n個不同的元素劃分成一些不相交的集合。開始時每個元素自成一個單元素集合然后按一定的規(guī)律將歸于同一組元素的集合合并。在此過程中要反復用到查詢某一個元素歸屬于哪個集合的運算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集union-find set。比如某公司今年校招全國總共招生 10 人西安招 4 人成都招 3 人武漢招 3 人10 個人來自不同的學校起先互不相識每個學生都是一個獨立的小團體現(xiàn)給這些學生進行編號{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}給以下數(shù)組用來存儲該小集體數(shù)組中的數(shù)字代表該小集體中具有成員的個數(shù)。負號下文解釋畢業(yè)后學生們要去公司上班每個地方的學生自發(fā)組織成小分隊一起上路于是西安學生小分隊s1{0,6,7,8}成都學生小分隊s2{1,4,9}武漢學生小分隊s3{2,3,5}就相互認識了10 個人形成了三個小團體。假設由三個群主 0、1、2 擔任隊長負責大家的出行。一趟火車之旅后每個小分隊成員就互相熟悉成為了一個朋友圈。從上圖可以看出編號 6、7、8 同學屬于 0 號小分隊該小分隊中有 4 人包含隊長 0編號為 4 和 9 的同學屬于 1 號小分隊該小分隊有 3 人包含隊長 1編號為 3 和 5 的同學屬于 2 號小分隊該小分隊有 3 個人包含隊長 2。仔細觀察數(shù)組中的內(nèi)容變化可以得出以下結(jié)論數(shù)組的下標對應集合中元素的編號數(shù)組中如果為負數(shù)負號代表根數(shù)字代表該集合中元素個數(shù)數(shù)組中如果為非負數(shù)代表該元素雙親在數(shù)組中的下標在公司工作一段時間后西安小分隊中 8 號同學與成都小分隊 1 號同學奇跡般地走到了一起兩個小圈子的學生相互介紹最后成為了一個小圈子現(xiàn)在 0 集合有 7 個人2 集合有 3 個人總共兩個朋友圈。通過以上例子可知并查集一般可以解決以下問題查找元素屬于哪個集合沿著數(shù)組表示的樹形關(guān)系一直找到根即樹中元素為負數(shù)的位置。查看兩個元素是否屬于同一個集合沿著數(shù)組表示的樹形關(guān)系往上一直找到樹的根如果根相同表明在同一個集合否則不在。將兩個集合歸并成一個集合將兩個集合中的元素合并。將一個集合名稱改成另一個集合的名稱。集合的個數(shù)遍歷數(shù)組數(shù)組中元素為負數(shù)的個數(shù)即為集合的個數(shù)。2. 并查集實現(xiàn)classUnionFindSet{public:// 初始時將數(shù)組中元素全部設置為-1UnionFindSet(size_t size):_ufs(size,-1){}// 給一個元素的編號找到該元素所在集合的名稱intFindRoot(intindex){// 如果數(shù)組中存儲的是負數(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ù)組中負數(shù)的個數(shù)即為集合的個數(shù)size_tCount()const{size_t count0;for(autoe:_ufs){if(e0)count;}returncount;}private:vectorint_ufs;};3. 并查集應用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;}}; 第7講：并查集
目錄本節(jié)目標1. 并查集原理2. 并查集實現(xiàn)3. 并查集應用省份數(shù)量等式方程的可滿足性本節(jié)目標并查集原理并查集實現(xiàn)并查集應用1. 并查集原理在一些應用問題中需要將n個不同的元素劃分成一些不相交的集合。開始時每個元素自成一個單元素集合然后按一定的規(guī)律將歸于同一組元素的集合合并。在此過程中要反復用到查詢某一個元素歸屬于哪個集合的運算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集union-find set。比如某公司今年校招全國總共招生 10 人西安招 4 人成都招 3 人武漢招 3 人10 個人來自不同的學校起先互不相識每個學生都是一個獨立的小團體現(xiàn)給這些學生進行編號{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}給以下數(shù)組用來存儲該小集體數(shù)組中的數(shù)字代表該小集體中具有成員的個數(shù)。負號下文解釋畢業(yè)后學生們要去公司上班每個地方的學生自發(fā)組織成小分隊一起上路于是西安學生小分隊s1{0,6,7,8}成都學生小分隊s2{1,4,9}武漢學生小分隊s3{2,3,5}就相互認識了10 個人形成了三個小團體。假設由三個群主 0、1、2 擔任隊長負責大家的出行。一趟火車之旅后每個小分隊成員就互相熟悉成為了一個朋友圈。從上圖可以看出編號 6、7、8 同學屬于 0 號小分隊該小分隊中有 4 人包含隊長 0編號為 4 和 9 的同學屬于 1 號小分隊該小分隊有 3 人包含隊長 1編號為 3 和 5 的同學屬于 2 號小分隊該小分隊有 3 個人包含隊長 2。仔細觀察數(shù)組中的內(nèi)容變化可以得出以下結(jié)論數(shù)組的下標對應集合中元素的編號數(shù)組中如果為負數(shù)負號代表根數(shù)字代表該集合中元素個數(shù)數(shù)組中如果為非負數(shù)代表該元素雙親在數(shù)組中的下標在公司工作一段時間后西安小分隊中 8 號同學與成都小分隊 1 號同學奇跡般地走到了一起兩個小圈子的學生相互介紹最后成為了一個小圈子現(xiàn)在 0 集合有 7 個人2 集合有 3 個人總共兩個朋友圈。通過以上例子可知并查集一般可以解決以下問題查找元素屬于哪個集合沿著數(shù)組表示的樹形關(guān)系一直找到根即樹中元素為負數(shù)的位置。查看兩個元素是否屬于同一個集合沿著數(shù)組表示的樹形關(guān)系往上一直找到樹的根如果根相同表明在同一個集合否則不在。將兩個集合歸并成一個集合將兩個集合中的元素合并。將一個集合名稱改成另一個集合的名稱。集合的個數(shù)遍歷數(shù)組數(shù)組中元素為負數(shù)的個數(shù)即為集合的個數(shù)。2. 并查集實現(xiàn)classUnionFindSet{public:// 初始時將數(shù)組中元素全部設置為-1UnionFindSet(size_t size):_ufs(size,-1){}// 給一個元素的編號找到該元素所在集合的名稱intFindRoot(intindex){// 如果數(shù)組中存儲的是負數(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ù)組中負數(shù)的個數(shù)即為集合的個數(shù)size_tCount()const{size_t count0;for(autoe:_ufs){if(e0)count;}returncount;}private:vectorint_ufs;};3. 并查集應用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;}};