目錄

1. 并查集的概念

2. 并查集的實現

3. 并查集的應用

3.1 力扣LCR 116. 省份數量

解析代碼1

解析代碼2

3.2 力扣990. 等式方程的可滿足性

解析代碼

本篇完。

---

寫在前面：

????????此高階數據結構系列，雖然放在⑤數據結構與算法專欄，但還是作為一個拓展學習，建議跳過第⑤序號跟著其它專欄序號學，當時是想著要期末考和考研的同學，考到圖才開這個專欄的吧，其他不急的同學可以在學完MySQL專欄后再看，此系列也放在了⑩其它高階數據結構專欄，這里簡單學習并查集是為了下一個數據結構“圖”的學習。

---

1. 并查集的概念

• 并查集是一種樹型的數據結構，用于處理一些不相交集合的合并及查詢問題。
• 并查集通常用森林來表示，森林中的每棵樹表示一個集合，樹中的結點對應一個元素。

????????雖然利用其它數據結構也能完成不相交集合的合并及查詢，但在數據量極大的情況下，其耗費的時間和空間也是極大的。

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

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

????????比如：某公司今年校招全國總共招生10人，西安招4人，成都招3人，武漢招3人，10個人來自不 同的學校，起先互不相識，每個學生都是一個獨立的小團體，現給這些學生進行編號：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 給以下數組用來存儲該小集體，數組中的數字代表：該小集體中具有成員的個 數。數組中某個位置的值為負數，表示該位置是樹的根，這個負數的絕對值表示的這棵樹（集合）中數據的個數，因為剛開始每個人各自屬于一個集合，所以將數組中的位置都初始化為-1。

????????畢業后，學生們要去公司上班，每個地方的學生自發組織成小分隊一起上路，于是：西安學生小分隊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 個人(包含隊長1)。 仔細觀察數組中內變化，可以得出以下結論：

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

????????在公司工作一段時間后，西安小分隊中8號同學與成都小分隊1號同學奇跡般的走到了一起，兩個小圈子的學生相互介紹，最后成為了一個小圈子：

????????現在0集合有7個人，2集合有3個人，總共兩個朋友圈。通過以上例子可知，并查集一般可以解決一下問題：

1. 查找元素屬于哪個集合：沿著數組表示樹形關系以上一直找到根（即：樹中中元素為負數的位置）。
2. 查看兩個元素是否屬于同一個集合：沿著數組表示的樹形關系往上一直找到樹的根，如果根相同表明在同一個集合，否則不在。
3. 將兩個集合歸并成一個集合：將兩個集合中的元素合并，將一個集合名稱改成另一個集合的名稱。
4. 集合的個數：遍歷數組，數組中元素為負數的個數即為集合的個數。

---

2. 并查集的實現

代碼實現還是很簡單的，直接放出代碼：（建議復制到自己編譯器跟著注釋一起看）

#pragma once#include <iostream>
#include <vector>
using namespace std;class UnionFindSet
{
private:vector<int> _ufs;public:UnionFindSet(size_t size) // 初始時，將數組中元素全部設置為1: _ufs(size, -1){}int FindRoot(int index) // 給一個元素的編號，找到該元素所在集合的名稱{int root = index;while (_ufs[root] >= 0)   // 如果數組中存儲的是負數，找到，否則一直繼續{root = _ufs[root];}while (_ufs[index] >= 0) // 路徑壓縮{int parent = _ufs[index];_ufs[index] = root;index = parent;}return index;}bool InSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}bool Union(int x1, int x2) // 合并兩個集合{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2) // x1已經與x2在同一個集合return false;if (abs(_ufs[root1]) < abs(_ufs[root2])) // 控制數據量小的往大的集合合并swap(root1, root2);_ufs[root1] += _ufs[root2]; // 負號代表根，數字代表該集合中元素個數_ufs[root2] = root1; // 將其中一個集合名稱改變成另外一個return true;}size_t Count() const  // 數組中負數的個數，即為集合的個數{size_t count = 0;for (auto e : _ufs){if (e < 0)++count;}return count;}
};void TestUFS()
{UnionFindSet u(10);u.Union(0, 6);u.Union(7, 6);u.Union(7, 8);u.Union(1, 4);u.Union(4, 9);u.Union(2, 3);u.Union(2, 5);u.FindRoot(6);u.FindRoot(9);cout << u.Count() << endl;
}

---

3. 并查集的應用

直接復制上面并查集的代碼到力扣寫兩道題：

3.1 力扣LCR 116. 省份數量

LCR 116. 省份數量

難度 中等

有?n?個城市，其中一些彼此相連，另一些沒有相連。如果城市?a?與城市?b?直接相連，且城市?b?與城市?c?直接相連，那么城市?a?與城市?c?間接相連。

省份?是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個?n x n?的矩陣?isConnected?，其中?isConnected[i][j] = 1?表示第?i?個城市和第?j?個城市直接相連，而?isConnected[i][j] = 0?表示二者不直接相連。

返回矩陣中?省份?的數量。

示例 1：

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

示例 2：

輸入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出：3

提示：

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j]?為?1?或?0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

注意：本題與主站 547?題相同：?547. 省份數量

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {}
};

---

解析代碼1

直接復制并查集過來：

class UnionFindSet
{
private:vector<int> _ufs;public:UnionFindSet(size_t size) // 初始時，將數組中元素全部設置為1: _ufs(size, -1){}int FindRoot(int index) // 給一個元素的編號，找到該元素所在集合的名稱{int root = index;while (_ufs[root] >= 0)   // 如果數組中存儲的是負數，找到，否則一直繼續{root = _ufs[root];}while (_ufs[index] >= 0) // 路徑壓縮{int parent = _ufs[index];_ufs[index] = root;index = parent;}return index;}bool InSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}bool Union(int x1, int x2) // 合并兩個集合{int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2) // x1已經與x2在同一個集合return false;if (abs(_ufs[root1]) < abs(_ufs[root2])) // 控制數據量小的往大的集合合并swap(root1, root2);_ufs[root1] += _ufs[root2]; // 負號代表根，數字代表該集合中元素個數_ufs[root2] = root1; // 將其中一個集合名稱改變成另外一個return true;}size_t Count() const  // 數組中負數的個數，即為集合的個數{size_t count = 0;for (auto e : _ufs){if (e < 0)++count;}return count;}
};class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {UnionFindSet ufs(isConnected.size());for (size_t i = 0; i < isConnected.size(); ++i){for (size_t j = 0; j < isConnected[i].size(); ++j){if (isConnected[i][j] == 1) // 合并集合{ufs.Union(i, j);}}}return ufs.Count();}
};

---

解析代碼2

用數組模擬并查集：

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {vector<int> ufs(isConnected.size(), -1); // 手動控制并查集auto findRoot = [&ufs](int x) // 查找根{while(ufs[x] >= 0)x = ufs[x];return x;};for(size_t i = 0; i < isConnected.size(); ++i){for(size_t j = 0; j < isConnected[i].size(); ++j){if(isConnected[i][j] == 1) // 合并集合{int root1 = findRoot(i);int root2 = findRoot(j);if (root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}}int cnt = 0;for(auto e : ufs){if(e < 0)++cnt;}return cnt;}
};

---

3.2 力扣990. 等式方程的可滿足性

990. 等式方程的可滿足性

難度 中等

給定一個由表示變量之間關系的字符串方程組成的數組，每個字符串方程?equations[i]?的長度為?4，并采用兩種不同的形式之一："a==b"?或?"a!=b"。在這里，a 和 b 是小寫字母（不一定不同），表示單字母變量名。

只有當可以將整數分配給變量名，以便滿足所有給定的方程時才返回?true，否則返回?false。?

示例 1：

輸入：["a==b","b!=a"]
輸出：false
解釋：如果我們指定，a = 1 且 b = 1，那么可以滿足第一個方程，但無法滿足第二個方程。沒有辦法分配變量同時滿足這兩個方程。

示例 2：

輸入：["b==a","a==b"]
輸出：true
解釋：我們可以指定 a = 1 且 b = 1 以滿足滿足這兩個方程。

示例 3：

輸入：["a==b","b==c","a==c"]
輸出：true

示例 4：

輸入：["a==b","b!=c","c==a"]
輸出：false

示例 5：

輸入：["c==c","b==d","x!=z"]
輸出：true

提示：

1. 1 <= equations.length <= 500
2. equations[i].length == 4
3. equations[i][0]?和?equations[i][3]?是小寫字母
4. equations[i][1]?要么是?'='，要么是?'!'
5. equations[i][2]?是?'='

class Solution {
public:bool equationsPossible(vector<string>& equations) {}
};

---

解析代碼

并查集的變形，思路：

1. 將所有"=="兩端的字符合并到一個集合中。
2. 檢測"!=" 兩端的字符是否在同一個集合中，如果在，不滿足，如果不在，滿足。

class Solution {
public:bool equationsPossible(vector<string>& equations) {vector<int> ufs(26, -1);auto findRoot = [&ufs](int x){while(ufs[x] >= 0)x = ufs[x];return x;};for(auto& e : equations) // 第一遍，先把相等的值加到一個集合中{if(e[1] == '='){int root1 = findRoot(e[0] - 'a');int root2 = findRoot(e[3] - 'a');if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}for(auto& e : equations) // 第二遍，判斷相等在不在一個集合，在就相悖了{if(e[1] == '!'){int root1 = findRoot(e[0] - 'a');int root2 = findRoot(e[3] - 'a');if(root1 == root2)return false;}}return true;}
};

---

本篇完。

這里簡單學習并查集更多是為了下一個數據結構“圖”的學習，一些競賽的OJ也會用到并查集。