---

前言

??其實我一開始是想直接講圖的，但是但是考慮的圖的 Kruskal 算法要用到，就先講解下并查集吧！

---

一、何為并查集？

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

這可能太抽象了，我們舉個具體的例子：

??以朋友圈為例，現在有10個人（從0開始編號），剛開始這10個人互不認識，所以各自屬于一個集合

??并查集會用一個數組來表示這10個人之間的關系，數組的下標對應就是這10個人的編號，剛開始時數組中的元素都初始化為-1

數組中某個位置的值為負數，表示該位置是樹的根，這個負數的絕對值表示的這棵樹（集合）中數據的個數，因為剛開始每個人各自屬于一個集合，所以將數組中的位置都初始化為-1

??后來這10個人之間通過相互認識，最終形成了三個朋友圈

??此時并查集數組中各個位置的值如下

數組中某個位置的值為非負數，表示該位置不是樹的根，這個非負數的值就是這個結點的父結點的編號

??后來4號和8號又通過某種機遇互相認識了，這時他們所在的兩個集合就需要進行合并，最終就變成了兩個朋友圈

??需要注意的是，在根據兩個元素合并兩個集合時，需要先分別找到這兩個元素所在集合的根結點，然后再將一個集合合并到另一個集合，并且合并后需要更新數組中根結點的值

為什么要找根節點？

1. 如果這兩個元素所在集合的根結點相同，說明這兩個元素本身就在同一個集合，無需合并
2. 合并集合后需要更新這兩個集合的根結點的值

??而要判斷兩個元素是否在同一個集合，也就是判斷這兩個元素所在集合的根結點是否相同

二、并查集的實現？

??首先我們要想元素的下標是否對應，如果無法對應的話，我們一般利用容器 map 來存儲元素的下標映射

template<class T>
class UnionFindSet
{
public:UnionFindSet(const T* a, size_t n){for (size_t i = 0 ; i < n ; i++) {_a.push_back(a[i]);_indexMap[a[i]] = i;}}
private:vector<T> _a; // 編號找人map<T, int> _indexMap;// 人找編號
};

??不過在這里，我們假設給的就是下標，也就是說私有成員就只有一個 vector< int > _ufs 了

并查集的初始化

??并查集中會用一個數組來維護各個結點之間的關系，在初始化并查集時，根據元素的個數開辟數組空間，并將數組中的元素初始化為 -1 即可

//構造函數
UnionFindSet(int n):_ufs(n, -1) //初始時各個元素自成一個集合
{}

查找元素所在的集合

查找邏輯如下：

• 如果元素對應下標位置存儲的是負數，則說明該元素即為根結點，返回該元素即可。
• 如果元素對應下標位置存儲的是非負數，則跳轉到其父結點的位置繼續查找根結點。

    int FindRoot(int x){int root = x;while (_ufs[root] >= 0){root = _ufs[root];}return root;}

判斷兩個元素是否在同一個集合

    bool isInset(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}

合并兩個元素所在的集合

合并邏輯如下：

• 分別找到兩個元素所在集合的根結點。
• 如果這兩個元素所在集合的根結點相同，則無需合并，如果這兩個元素所在集合的根結點不同，則將小集合合并到大集合上。
• 將小集合根結點的值累加到大集合的根結點上，使得大集合根結點的值的絕對值等于兩個集合中元素的總數。
• 將小集合根結點的值改為大集合根結點的編號，也就是讓小集合的根結點作為大集合根結點的孩子，使得兩個集合變為一個集合。

    // 合并兩個集合void Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 如果本身就在一個集合，那么無需合并if (root1 == root2) return ;// 合并的時候，作為孩子，其深度會增加一層// 因此，理論上來說，數據量小的作孩子// 如果有需求下標小的作根，則交換一下root// if (root1 > root2) swap(root1, root2); // 按照下標大小if (abs(_ufs[root1]) < abs(_ufs[root2])) swap(root1, root2); // 按照數據量大小// 如果不在同一個集合，則默認認為把x2代表集合合并到x1上，即x1作根，x2作子_ufs[root1] += _ufs[root2];// 將x2代表集合的名稱改為x1_ufs[root2] = root1;}

獲取并查集中集合的個數

??要獲取并查集中集合的個數，本質就是統計數組中負值（根結點）的個數

    size_t SetSize(){size_t size = 0;for (size_t i = 0 ; i < _ufs.size() ; i++){if (_ufs[i] < 0) size++;}return size;}

并查集的路徑壓縮

??當數據量很大的時候，并查集中樹的層數可能會變得很高，這時再查找一個元素所在集合的根結點時就需要往上走很多層，這時可以考慮進行路徑壓縮

??路徑壓縮一般會在查找根結點時進行，當根據一個結點查找其根結點時，該路徑上所有的結點都會被壓縮，最終這些結點會直接被掛在根結點下，下次再根據這些結點查找根結點時就能快速找到根結點

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

三、來兩道題練練手？

省份的數量

LCR 116. 省份數量

思路其實是很明確的：

1. 定義一個長度為 n 的數組充當并查集，并將數組中的元素初始化為 -1，表示各個城市各自是一個省份。
2. 根據所給矩陣，對并查集中的各個集合進行合并。
3. 并查集中集合的個數即為省份的數量

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]){ufs.Union(i, j);}}}return ufs.SetSize();}};

等式方程的可滿足性

990. 等式方程的可滿足性

思路其實也是很明確的：

1. 定義一個長度為26（變量為小寫字母）的數組充當并查集，并將數組中的元素初始化為-1，表示各個字母只有自己等于自己。
2. 根據字符串方程組中的等式，對并查集中的各個集合進行合并（每個集合中的元素都是相等的）。
3. 根據并查集，對字符串方程組中的不等式進行驗證，如果兩個不相等的變量出現在同一個集合中，則返回 false 。

class Solution
{
public:bool equationsPossible(vector<string>& equations){UnionFindSet ufs(26);for (const auto& str : equations){if (str[1] == '='){ufs.Union(str[0] - 'a', str[3] - 'a');}}for (const auto& str : equations){if (str[1] == '!'){int root1 = ufs.FindRoot(str[0] - 'a');int root2 = ufs.FindRoot(str[3] - 'a');if (root1 == root2) return false;}}return true;}
};

---

總結

??其實，從這里開始的數據結構就比較困難了
??圖、跳表、B樹，它們要來了！！！