🏆個人主頁：企鵝不叫的博客

創(chuàng)新互聯(lián)建站專業(yè)為企業(yè)提供城子河網(wǎng)站建設、城子河做網(wǎng)站、城子河網(wǎng)站設計、城子河網(wǎng)站制作等企業(yè)網(wǎng)站建設、網(wǎng)頁設計與制作、城子河企業(yè)網(wǎng)站模板建站服務，十年城子河做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡服務。

? 🌈專欄

• C語言初階和進階
• C項目
• Leetcode刷題
• 初階數(shù)據(jù)結構與算法
• C++初階和進階
• 《深入理解計算機操作系統(tǒng)》
• 《高質量C/C++編程》
• Linux

?? 博主碼云gitee鏈接：代碼倉庫地址

?若有幫助可以【關注+點贊+收藏】，大家一起進步！

💙系列文章💙

---

文章目錄

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

---

💎一、概念

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

舉例：現(xiàn)在有十個元素，每個元素的值都初始化為-1

現(xiàn)在將0，3，4這三個元素構成一個集合，我們讓0為根，將根放到3和4下標對應的元素上，同時將3和4原本對應的元素加給0下標對應的元素

同理將2，5，7，8和1，6，9構成一個集合，默認2和1為根

同理將0集合和1集合合并，默認0是根

總結：

1. 數(shù)組的下標對應集合中元素的編號
2. 數(shù)組中如果為負數(shù)，負號代表根，數(shù)字的絕對值代表該集合中元素個數(shù)
3. 數(shù)組中如果為非負數(shù)，代表該元素雙親在數(shù)組中的下標

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

底層使用vector實現(xiàn)，并且全部初始化為-1

class UnionFindSet {public:
	UnionFindSet(int sz)
		:_ufs(sz, -1) {}
private:
	vector_ufs;
};

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

1. 當元素對應的下標對應的內容為正數(shù)時（也就是該元素不為根），我們需要更新該下標，也就是index=_ufs[index]，讓自己成為雙親
2. 繼續(xù)判斷，如果對應內容為負數(shù)，說明該下標是根，直接返回

int FindRoot(int x){while (_ufs[x] >= 0) {//更新親人
        x = _ufs[x];
    }
    return x;
}

壓縮路徑

并查集的訪問是依靠數(shù)組下標實現(xiàn)的隨機訪問，時間復雜度為O(1)，只有數(shù)據(jù)樣本量極大的時候，可以考慮路勁壓縮

//查找元素屬于哪個集合
	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.合并兩個集合

1. 找到兩個集合對應的根
2. 如果兩個根相等說明兩個集合相等，如果兩個根不相等則讓其中一個根歸并到一個根的下面，更新新的雙親的內容和被并入的根的內容

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.判斷兩個元素是否在同一個集合當中

如果兩個集合根相等說明在同一個集合當中

bool isUnion(int x, int y) {return FindRoot(x) == FindRoot(y);
	}

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

遍歷一遍數(shù)組，統(tǒng)計內容為負數(shù)的下標的個數(shù)，即統(tǒng)計了集合個數(shù)

int size() {int count = 0;
		for (auto e : _ufs) {	if (e< 0) {		++count;
			}
		}
		return count;
	}

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

傳送門

思路：遍歷所有元素，將相關聯(lián)的數(shù)放到同一個集合當中，最后統(tǒng)計集合數(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. 等式方程的可滿足性

傳送門

思路：如果兩個字符相等，則放入同一個集合之中。
如果兩個字符不相等，它們應當在不同的集合中，此時查找它們所在集合的根，如果相同則說明這兩個字符在同一個集合中，返回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);
//第一遍遍歷，將相同的值放到同一個集合當中
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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

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

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

廣告

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