目錄
一，什么是并查集
二，并查集的結構?
三，并查集的代碼實現?
1，并查集的大致結構和初始化
2，find操作?
3，Union操作
4，優化?
小結：
四，并查集的應用場景
省份數量[OJ題]?
一，什么是并查集
核心概念：并查集是一種 用于管理元素分組?的數據結構。
在一些應用問題中，需將n個不同的元素劃分成一些不相交的集合，開始時，n個元素各自成一個集合，然后按照一定規律將部分集合合成一個集合，也就是集合合并。并查集（union-find)適合來描述這類問題。
對于并查集，我們可以將它看成是一個森林，森林是由多棵樹組成的，并查集中的一個個集合就可以看作是樹。
示例：
二，并查集的結構?
并查集的存儲結構和樹的雙親表示法相似。
所謂雙親表示法，就是在樹的節點中，只存儲父節點的指針，不存儲孩子節點的指針。通過指針可以找到父節點。因為對于一顆樹來說，可能有多個孩子 ，但只有一個父節點。
?
對于上圖中：
節點0的數組值為-4，說明該節點為根節點。
節點6的數組值為0，說明該節點的父節點為0。
節點7的數組值為0，說明該節點的父節點為0。
節點8的數組值為0，說明該節點的父節點為0。
三，并查集的代碼實現?
并查集主要支持一下操作：
- 查詢（find），查詢一個元素在哪個集合中。
- 合并（union)，將兩個集合合并為一個。
1，并查集的大致結構和初始化
class UnionFind
{
public:
?? ?UnionFind(size_t n)
?? ??? ?:_ufs(n,-1)
?? ?{}?? ?//......
private:
?? ?vector<int> _ufs;
};
2，find操作?
在并查集中找到包含x的根
int findRoot(int x)
{
?? ?int root = x;?? ?while (_ufs[root] >= 0)
?? ??? ?root = _ufs[root];?? ?return root;
}?
3，Union操作
合并兩個集合
void Union(int x1, int x2)
{
?? ?int root1 = findRoot(x1);
?? ?int root2 = findRoot(x2);
?? ?if (root1 == root2)
?? ??? ?return; //在同一個集合中?? ?//這里在合并的時候采用數據量小的向數據量大的合并
?? ?//也就是小樹向大樹合并
?? ?if (abs(_ufs[root1]) < abs(_ufs[root2]))//root1節點更少
?? ?{
?? ??? ?_ufs[root2] += _ufs[root1];
?? ??? ?_ufs[root1] = root2; ? //小樹合并到大樹
?? ?}
?? ?else
?? ?{
?? ??? ?//root2節點更少
?? ??? ?_ufs[root1] += _ufs[root2];
?? ??? ?_ufs[root2] = root1;
?? ?}
}
4，優化?
當樹比較高時，我們在反復查某個節點的根節點時，每次都會花費大量時間。
優化方法：路徑壓縮，只要查找某個節點一次，就將查找路徑上的所有節點掛到根節點下面。
如圖：查找D的根A，查找路徑上包含節點B，將節點D和節點B直接掛在根節點A的下面。
//路徑壓縮
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;
}小結：
上述實現的并查集，支持連續元素。如果是處理非連續元素，需要使用哈希表代替數組（需額處理元素與索引的映射）。
核心思路：
- 哈希映射：用
unordered_map將任意類型元素映射為連續整數ID，內部用數組管理父節點動態擴容：自動添加新元素，無需預先指定規模。
模板化：支持泛型數據類型（如
string等）。
四，并查集的應用場景
連通性檢測：判斷網絡中兩個節點是否連通。
最小生成樹（Kruskal算法）：動態合并邊，避免環。
社交網絡分組：快速合并好友關系，查詢是否屬于同一社交圈。
總結：
并查集通過高效的查找與合并操作，成為處理動態連通性問題的核心數據結構。其優化方法（路徑壓縮、按秩合并）確保了接近常數的單次操作時間復雜度，適用于大規模數據場景。
其中的按秩合并就是合并集合時小樹向大樹合并。
省份數量[OJ題]?
題目鏈接：LCR 116. 省份數量 - 力扣（LeetCode）
?isConnected[i][j]=1，表示城市i和j連通，連通的城市為一個省份。用并查集將連通的數據放入一個集合，再統計最后的集合個數即可。
class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int n=isConnected.size();vector<int> _ufs(n,-1);//查找根auto find=[&](int x)->int{int root=x;while(_ufs[root]>=0)root=_ufs[root];return root;};for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(isConnected[i][j]==1){//合并i和j集合int rooti=find(i),rootj=find(j);if(rooti!=rootj){_ufs[rooti]+=_ufs[rootj];_ufs[rootj]=rooti;}}}//統計集合數int ret=0;for(auto x:_ufs){if(x<0)ret++;}return ret;}
};冗余連接[OJ題]
題目鏈接：684. 冗余連接 - 力扣（LeetCode）
class Solution {
public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {//遍歷edges數組//將在同一條邊中的兩個頂點放入一個集合//如果這條邊的兩個頂點已經在同一個集合中，加入這條邊后，會出現環 ，返回這條邊vector<int> ufs(1010);int sz=edges.size();//初始化時各元素自成一個集合，自己就是根for(int i=0;i<sz;i++)ufs[i]=i;for(int j=0;j<sz;j++){//找到邊的兩個頂點所在的集合，也就是根節點int root1=find(edges[j][0],ufs);int root2=find(edges[j][1],ufs);//如果在一個集合，加入這條邊后，會出現環if(root1==root2)return edges[j];else{//兩個集合獨立，合并兩個集合ufs[root1]=root2;}}return {0,0};}int find(int num,vector<int>& ufs){int root=num;while(ufs[root]!=root)root=ufs[root];return root;}
};等式方程的可滿足性[OJ題]
本題鏈接：990. 等式方程的可滿足性 - 力扣（LeetCode）
class Solution {
public:bool equationsPossible(vector<string>& equations) {//并查集vector<int> ufs(26,-1);auto findroot=[&](int x){int parent=x;while(ufs[parent]>=0)parent=ufs[parent];return parent;};//將相等的放入同一集合中for(auto& str:equations)if(str[1]=='='){int root1=findroot(str[0]-'a');int root2=findroot(str[3]-'a');if(root1!=root2){ufs[root1]+=ufs[root2];ufs[root2]=root1;}}//遇到！，如果在同一個集合，返回falsefor(auto& str:equations){if(str[1]=='!'){int root1=findroot(str[0]-'a');int root2=findroot(str[3]-'a');if(root1==root2)return false;}}return true;}
};?
![145，【5】 buuctf web [GWCTF 2019]mypassword](http://pic.xiahunao.cn/145，【5】 buuctf web [GWCTF 2019]mypassword)
