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

創新互聯建站專業為企業提供城子河網站建設、城子河做網站、城子河網站設計、城子河網站制作等企業網站建設、網頁設計與制作、城子河企業網站模板建站服務，十年城子河做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。

? 🌈專欄

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

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

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

💙系列文章💙

---

文章目錄

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

---

💎一、概念

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

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

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

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

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

總結：

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

💎二、實現 🏆1.框架

底層使用vector實現，并且全部初始化為-1

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

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

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

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

壓縮路徑

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

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

遍歷一遍數組，統計內容為負數的下標的個數，即統計了集合個數

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

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

傳送門

思路：遍歷所有元素，將相關聯的數放到同一個集合當中，最后統計集合數量即可

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;
}
};

---

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享名稱：【C++高階數據結構】并查集-創新互聯
網站地址：http://www.yijiale78.com/article12/deojgc.html

成都網站建設公司_創新互聯，為您提供軟件開發、網站內鏈、動態網站、商城網站、網站維護、搜索引擎優化

廣告

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