并查集
- 并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問題。
- 并查集通常用森林來表示，森林中的每棵樹表示一個集合，樹中的結(jié)點對應(yīng)一個元素。
說明一下： 雖然利用其他數(shù)據(jù)結(jié)構(gòu)也能完成不相交集合的合并及查詢，但在數(shù)據(jù)量極大的情況下，其耗費的時間和空間也是極大的。
并查集的原理
并查集的原理
以朋友圈為例，現(xiàn)在有10個人（從0開始編號），剛開始這10個人互不認(rèn)識，所以各自屬于一個集合。如下：
并查集會用一個數(shù)組來表示這10個人之間的關(guān)系，數(shù)組的下標(biāo)對應(yīng)就是這10個人的編號，剛開始時數(shù)組中的元素都初始化為-1。如下：
說明一下：
- 數(shù)組中某個位置的值為負(fù)數(shù)，表示該位置是樹的根，這個負(fù)數(shù)的絕對值表示的這棵樹（集合）中數(shù)據(jù)的個數(shù)，因為剛開始每個人各自屬于一個集合，所以將數(shù)組中的位置都初始化為-1。
后來這10個人之間通過相互認(rèn)識，最終形成了三個朋友圈。如下：
此時并查集數(shù)組中各個位置的值如下：
說明一下：
- 數(shù)組中某個位置的值為非負(fù)數(shù)，表示該位置不是樹的根，這個非負(fù)數(shù)的值就是這個結(jié)點的父結(jié)點的編號。
后來4號和8號又通過某種機(jī)遇互相認(rèn)識了，這時他們所在的兩個集合就需要進(jìn)行合并，最終就變成了兩個朋友圈。如下：
需要注意的是，在根據(jù)兩個元素合并兩個集合時，需要先分別找到這兩個元素所在集合的根結(jié)點，然后再將一個集合合并到另一個集合，并且合并后需要更新數(shù)組中根結(jié)點的值。
示意圖如下：
合并集合找根結(jié)點的原因：
- 如果這兩個元素所在集合的根結(jié)點相同，說明這兩個元素本身就在同一個集合，無需合并。
- 合并集合后需要更新這兩個集合的根結(jié)點的值。
而要判斷兩個元素是否在同一個集合，也就是判斷這兩個元素所在集合的根結(jié)點是否相同。
并查集的實現(xiàn)
并查集的實現(xiàn)
實現(xiàn)并查集時通常會實現(xiàn)如下接口：
- 初始化并查集。
- 查找元素所在的集合。
- 判斷兩個元素是否在同一個集合。
- 合并兩個元素所在的集合。
- 獲取并查集中集合的個數(shù)。
代碼如下：
//并查集
class UnionFindSet {
public:
//構(gòu)造函數(shù)
UnionFindSet(int n);
//查找元素所在的集合
int findRoot(int x);
//判斷兩個元素是否在同一個集合
bool inSameSet(int x1, int x2);
//合并兩個元素所在的集合
bool unionSet(int x1, int x2);
//獲取并查集中集合的個數(shù)
int getNum();
private:
vector<int> _ufs; //維護(hù)各個結(jié)點之間的關(guān)系
};
并查集中的數(shù)組：
- 數(shù)組的下標(biāo)依次對應(yīng)每個元素的編號。
- 數(shù)組中元素值為負(fù)數(shù)，表示下標(biāo)編號元素為根結(jié)點，負(fù)數(shù)的絕對值表示該集合中元素的個數(shù)。
- 數(shù)組中元素值為非負(fù)數(shù)，表示下標(biāo)編號元素的父結(jié)點的編號。
并查集的初始化
并查集的初始化
并查集中會用一個數(shù)組來維護(hù)各個結(jié)點之間的關(guān)系，在初始化并查集時，根據(jù)元素的個數(shù)開辟數(shù)組空間，并將數(shù)組中的元素初始化為-1即可。
代碼如下：
//構(gòu)造函數(shù)
UnionFindSet(int n)
:_ufs(n, -1) //初始時各個元素自成一個集合
{}
查找元素所在的集合
查找元素所在的集合
查找元素所在的集合，本質(zhì)就是查找元素所在集合的根結(jié)點。
查找邏輯如下：
- 如果元素對應(yīng)下標(biāo)位置存儲的是負(fù)數(shù)，則說明該元素即為根結(jié)點，返回該元素即可。
- 如果元素對應(yīng)下標(biāo)位置存儲的是非負(fù)數(shù)，則跳轉(zhuǎn)到其父結(jié)點的位置繼續(xù)查找根結(jié)點。
迭代方式實現(xiàn)如下：
//查找元素所在集合的根結(jié)點（迭代）
int findRoot(int x) {
int parent = x; //默認(rèn)當(dāng)前結(jié)點就是根結(jié)點
while (_ufs[parent] >= 0) { //當(dāng)前結(jié)點值不是負(fù)數(shù)則繼續(xù)向上找
parent = _ufs[parent];
}
return parent; //返回根結(jié)點
}
遞歸方式實現(xiàn)如下：
//查找元素所在集合的根結(jié)點（遞歸）
int findRoot(int x) {
return _ufs[x] < 0 ? x : findRoot(_ufs[x]);
}
判斷兩個元素是否在同一個集合
判斷兩個元素是否在同一個集合
要判斷兩個元素是否在同一個集合，本質(zhì)就是判斷這兩個元素所在集合的根結(jié)點是否相同。
代碼如下：
//判斷兩個元素是否在同一個集合
bool inSameSet(int x1, int x2) {
return findRoot(x1) == findRoot(x2);
}
合并兩個元素所在的集合
合并兩個元素所在的集合
合并邏輯如下：
- 分別找到兩個元素所在集合的根結(jié)點。
- 如果這兩個元素所在集合的根結(jié)點相同，則無需合并，如果這兩個元素所在集合的根結(jié)點不同，則將小集合合并到大集合上。
- 將小集合根結(jié)點的值累加到大集合的根結(jié)點上，使得大集合根結(jié)點的值的絕對值等于兩個集合中元素的總數(shù)。
- 將小集合根結(jié)點的值改為大集合根結(jié)點的編號，也就是讓小集合的根結(jié)點作為大集合根結(jié)點的孩子，使得兩個集合變?yōu)橐粋€集合。
代碼如下：
//合并兩個元素所在的集合
bool unionSet(int x1, int x2) {
int parent1 = findRoot(x1), parent2 = findRoot(x2); //分別找到兩個元素所在集合的根結(jié)點
if (parent1 == parent2) //兩個結(jié)點已經(jīng)位于同一集合
return false;
if (_ufs[parent1] > _ufs[parent2]) //讓parent1標(biāo)記大集合根結(jié)點，parent2標(biāo)記小集合根結(jié)點
swap(parent1, parent2);
//將小集合合并到大集合上
_ufs[parent1] += _ufs[parent2]; //將小集合根結(jié)點的值累加到大集合的根結(jié)點上
_ufs[parent2] = parent1; //將小集合根結(jié)點的值改為大集合根結(jié)點的編號
return true;
}
說明一下：
- 當(dāng)兩個集合需要合并時，盡量將小集合合并到大集合上，因為被合并的那個集合中的所有結(jié)點在合并后層數(shù)都會加一，所以這樣做的目的就是為了讓較少的結(jié)點層數(shù)加一，該操作不是必須的。
獲取并查集中集合的個數(shù)
獲取并查集中集合的個數(shù)
要獲取并查集中集合的個數(shù)，本質(zhì)就是統(tǒng)計數(shù)組中負(fù)值（根結(jié)點）的個數(shù)。
代碼如下：
//獲取并查集中集合的個數(shù)
int getNum() {
int count = 0; //統(tǒng)計根結(jié)點的個數(shù)
for (const int& val : _ufs) {
if (val < 0) //元素值為負(fù)數(shù)則為根結(jié)點
count++;
}
return count; //返回根結(jié)點的個數(shù)
}
并查集的路徑壓縮
并查集的路徑壓縮
當(dāng)數(shù)據(jù)量很大的時候，并查集中樹的層數(shù)可能會變得很高，這時在查找一個元素所在集合的根結(jié)點時就需要往上走很多層，這時可以考慮進(jìn)行路徑壓縮。
- 路徑壓縮一般會在查找根結(jié)點時進(jìn)行，當(dāng)根據(jù)一個結(jié)點查找其根結(jié)點時，該路徑上所有的結(jié)點都會被壓縮，最終這些結(jié)點會直接被掛在根結(jié)點下，下次再根據(jù)這些結(jié)點查找根結(jié)點時就能快速找到根結(jié)點。
迭代方式實現(xiàn)如下：
//查找元素所在集合的根結(jié)點（迭代）
int findRoot(int x) {
int root = x; //默認(rèn)當(dāng)前結(jié)點就是根結(jié)點
while (_ufs[root] >= 0) { //當(dāng)前結(jié)點值不是負(fù)數(shù)則繼續(xù)向上找
root = _ufs[root];
}
//路徑壓縮
while (_ufs[x] >= 0) { //遍歷從根結(jié)點到x結(jié)點路徑上的所有結(jié)點
int parent = _ufs[x];
_ufs[x] = root; //將結(jié)點的父親改為根結(jié)點
x = parent;
}
return root; //返回根結(jié)點
}
遞歸方式實現(xiàn)如下：
//查找元素所在集合的根結(jié)點（遞歸）
int findRoot(int x) {
int parent = x; //默認(rèn)當(dāng)前結(jié)點就是根結(jié)點
if (_ufs[x] >= 0) { //當(dāng)前結(jié)點值不是負(fù)數(shù)則繼續(xù)向上找
parent = findRoot(_ufs[x]); //找到根結(jié)點
_ufs[x] = parent; //將當(dāng)前結(jié)點的父親改為根結(jié)點（路徑壓縮）
}
return parent; //返回根結(jié)點
}
元素的編號問題
元素編號問題
上面在實現(xiàn)并查集時，默認(rèn)元素的編號都是從0開始依次遞增的，但用戶所給的編號可能并不是從0開始的，也不是連續(xù)的，甚至可能不是數(shù)字。
這時可以以模板的方式來實現(xiàn)并查集：
- 在初始化并查集時，根據(jù)所給元素建立元素與數(shù)組下標(biāo)之間的映射關(guān)系。
- 在查找元素所在集合的根結(jié)點時，先根據(jù)所給元素得到其對應(yīng)的數(shù)組下標(biāo)，然后再進(jìn)行查找。
代碼如下：
//并查集
template<class T>
class UnionFindSet {
public:
//構(gòu)造函數(shù)
UnionFindSet(const vector<T>& v)
:_ufs(v.size(), -1) //初始時各個元素自成一個集合
{
//建立元素與數(shù)組下標(biāo)之間的映射關(guān)系
for (int i = 0; i < v.size(); i++) {
_indexMap[v[i]] = i;
}
}
//查找元素所在集合的根結(jié)點（迭代）
int findRoot(const T& x) {
int parent = _indexMap[x]; //默認(rèn)當(dāng)前結(jié)點就是根結(jié)點
while (_ufs[parent] >= 0) { //當(dāng)前結(jié)點值不是負(fù)數(shù)則繼續(xù)向上找
parent = _ufs[parent];
}
return parent; //返回根結(jié)點
}
//合并兩個元素所在的集合
bool unionSet(const T& x1, const T& x2) {
int parent1 = findRoot(x1), parent2 = findRoot(x2); //分別找到兩個元素所在集合的根結(jié)點
if (parent1 == parent2) //兩個結(jié)點已經(jīng)位于同一集合
return false;
if (_ufs[parent1] > _ufs[parent2]) //讓parent1標(biāo)記大集合根結(jié)點，parent2標(biāo)記小集合根結(jié)點
swap(parent1, parent2);
//將小集合合并到大集合上
_ufs[parent1] += _ufs[parent2]; //將小集合根結(jié)點的值累加到大集合的根結(jié)點上
_ufs[parent2] = parent1; //將小集合根結(jié)點的值改為大集合根結(jié)點的編號
return true;
}
//獲取并查集中集合的個數(shù)
int getNum() {
int count = 0; //統(tǒng)計根結(jié)點的個數(shù)
for (const int& val : _ufs) {
if (val < 0) //元素值為負(fù)數(shù)則為根結(jié)點
count++;
}
return count; //返回根結(jié)點的個數(shù)
}
private:
vector<int> _ufs; //維護(hù)各個結(jié)點之間的關(guān)系
unordered_map<T, int> _indexMap; //建立元素與數(shù)組下標(biāo)之間的映射關(guān)系
};
這樣在使用并查集時就可以傳入任意類型的元素了。如下：
int main() {
vector<string> v = { "張三", "李四", "王五", "趙六", "田七", "周八", "吳九" };
UnionFindSet<string> ufs(v);
cout << ufs.getNum() << endl; //7
ufs.unionSet("張三", "李四");
ufs.unionSet("王五", "趙六");
cout << ufs.getNum() << endl; //5
ufs.unionSet("張三", "趙六");
cout << ufs.getNum() << endl; //4
return 0;
}
并查集的題目
省份的數(shù)量
省份的數(shù)量
題目描述：
??有
n
n
n 個城市，其中一些彼此相連，另一些沒有相連，如果城市
a
a
a 與城市
b
b
b 直接相連，且城市
b
b
b 與城市
c
c
c 直接相連，那么城市
a
a
a 與城市
c
c
c 間接相連。省份是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。
??給你一個
n
×
n
n \times n
n×n 的矩陣，其中
i
s
C
o
n
n
e
c
t
e
d
[
i
]
[
j
]
=
1
isConnected[i][j]=1
isConnected[i][j]=1 表示第
i
i
i 個城市和第
j
j
j 個城市直接相連，而
i
s
C
o
n
n
e
c
t
e
d
[
i
]
[
j
]
=
0
isConnected[i][j]=0
isConnected[i][j]=0 表示二者不直接相連。返回矩陣中省份的數(shù)量。
解題步驟：文章來源：http://www.zghlxwxcb.cn/news/detail-438888.html
- 定義一個長度為 n n n 的數(shù)組充當(dāng)并查集，并將數(shù)組中的元素初始化為-1，表示各個城市各自是一個省份。
- 根據(jù)所給矩陣，對并查集中的各個集合進(jìn)行合并。
- 并查集中集合的個數(shù)即為省份的數(shù)量。
代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-438888.html
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
//1、初始化并查集
int n = isConnected.size();
vector<int> ufs(n, -1);
auto findRoot = [&ufs](int x)->int {
int parent = x;
while (ufs[parent] >= 0) {
parent = ufs[parent];
}
return parent;
};
//2、根據(jù)所給矩陣合并集合
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1) { //城市相連
int parent1 = findRoot(i), parent2 = findRoot(j);
if (parent1 != parent2) { //需要合并
ufs[parent2] = parent1;
}
}
}
}
//3、統(tǒng)計并查集中集合的個數(shù)
int count = 0;
for (const int& e : ufs) {
if (e < 0)
count++;
}
return count;
}
};
說明一下：
- 在使用并查集解題時不需要實現(xiàn)一個完整的并查集，根據(jù)題目要求實現(xiàn)需要用到的邏輯即可。
等式方程的可滿足性
等式方程的可滿足性
題目描述：
??給定一個由表示變量之間關(guān)系的字符串方程組成的數(shù)組，每個字符串方程
e
q
u
a
t
i
o
n
s
[
i
]
equations[i]
equations[i] 的長度為4，并采用兩種不同的形式之一：“
a
a
a==
b
b
b” 或 “
a
a
a!=
b
b
b”。在這里
a
a
a 和
b
b
b 是小寫字母（不一定不同），表示單字母變量名。
??只有當(dāng)可以將整數(shù)分配給變量名，以便滿足所有給定的方程時才返回
t
r
u
e
true
true ，否則返回
f
a
l
s
e
false
false 。
解題步驟：
- 定義一個長度為26（變量為小寫字母）的數(shù)組充當(dāng)并查集，并將數(shù)組中的元素初始化為-1，表示各個字母只有自己等于自己。
- 根據(jù)字符串方程組中的等式，對并查集中的各個集合進(jìn)行合并（每個集合中的元素都是相等的）。
- 根據(jù)并查集，對字符串方程組中的不等式進(jìn)行驗證，如果兩個不相等的變量出現(xiàn)在同一個集合中，則返回 f a l s e false false 。
代碼如下：
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
//1、初始化并查集
vector<int> ufs(26, -1);
auto findRoot = [&ufs](int x)->int {
int parent = x;
while (ufs[parent] >= 0) {
parent = ufs[parent];
}
return parent;
};
//2、根據(jù)字符串方程組中的等式合并集合
for (const string& s : equations) {
if (s[1] == '=') { //等式
int parent1 = findRoot(s[0] - 'a'), parent2 = findRoot(s[3] - 'a');
if (parent1 != parent2) { //需要合并
ufs[parent2] = parent1;
}
}
}
//3、根據(jù)并查集驗證字符串方程組中的不等式
for (const string& s : equations) {
if (s[1] == '!') { //不等式
int parent1 = findRoot(s[0] - 'a'), parent2 = findRoot(s[3] - 'a');
if (parent1 == parent2) { //在同一個集合
return false;
}
}
}
return true;
}
};
到了這里，關(guān)于高階數(shù)據(jù)結(jié)構(gòu) ——— 并查集的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
