并查集（并茶幾）的應用

一、What‘s that？

并查集是一種樹型的數據結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。 ——百度百科

二、How to uphold

0.我們的需求

一開始我們擁有一個集族（集合的集合），集族中所有集合不相交，每個集合有且僅有一個元素。

百度百科告訴我們 ：
并查集至少需要支持兩種操作：

1.合并某兩個集合a,b。

2.詢問兩個元素x,y是否屬于同一集合。

1.可行的想法

我們能夠想到用樹的結構存儲這樣一個集合，每一次的合并就相當于將其中一棵樹的根的父親改為另一子樹的根的編號。

記錄一個值f[i]表示i的父親結點（當i為根時，將父親視為自己，也就是f[i]=i）。
所以我們有一個性質：若f[i]=i，則i為此樹的根。
初始時所有的點的f[i]=i。

2.初始化

void init(){ for (int i=1;i<=n;i++) f[i]=i; }

3.查找樹根

那么如何尋找一個結點所在的樹的根呢？
Q：只要沿著f[i]一直向上跳到f[i]=i，此時的i結點便是樹根

int find(int x){ return f[x]==x?x:find(f[x]);} //1.如果f[x]==x，返回樹根為x; 2.如果f[x]!=x，繼續搜索x的祖先f[x]是否為樹根

維護合并

接下來維護集合的合并操作。
例如我們需要合并2和6所在的集合：

那么只需要將2子樹的根結點（1結點），與6子樹的根結點（5結點）連接即可：

void Union(int x,int y) {int xx=find(x),yy=find(y); //找到兩樹的根 if (xx!=yy) { f[yy]=xx; } //如果兩樹的根不同，合并兩棵樹 }

5.優化原始并茶幾

這就是并查集的“初始版本”了。
但我們發現它每一次的詢問時間復雜度可能達到O(n)。
因為當數據退化為一條鏈的時候，每一次對鏈尾的find的次數是O(size)

a.按秩合并

所以這樣一個數據結構在我們看來并不優，嘗試著優化。
我們發現一棵較高的樹x與一棵較低的樹y合并時，應該從較高的樹向較低的樹連邊，使其合并。是為按秩合并。（f[y]=x）

void Union(int x,int y) {int xx=find(x),yy=find(y); if (xx!=yy) { if (rank[xx]>rank[yy]) f[yy]=xx; //按秩合并，rank[xx]表示xx樹的高度 else f[xx]=yy; } }

這一優化據說能將時間復雜度降低為O(logn)

b.路徑壓縮

還有一個更簡單且高效的優化：路徑壓縮。
我們發現我們并不需要知道我們如何沿著f[i]向上跳，我們只需要找到最終的root就能夠完成任務了。所以我們把f[i]的定義改為記錄i的祖先結點的編號，在我們每一次find樹根的時候，更新f[i]的值為樹根，如此一來，當我們再次find(i)時，就能一步找到樹根的位置。

int find(int x){ return f[x]=(f[x]==x?x:find(f[x])); } //將得到的值直接賦予f[x]即可

這樣路徑壓縮優化過后，每一次find時間復雜度理論上為O(1)，union的時間也是O(1)，這樣我們就完成了一個能夠維護部分集合操作的優秀數據結構。
（一般情況下，路徑壓縮后的時間復雜度已經能達到O(1)，所以通常不會寫較為麻煩的按秩合并，so以下的所有代碼舍棄按秩合并的優化。）

三、How to use it？

并查集是一個短小精悍的數據結構，因此在各類競賽中的出現頻率還是比較高的，并查集也有一些巧妙的思路與方法。

一般的并查集能夠維護：

子樹內信息。（通常在樹根上維護）

從子結點到根的信息。

1.首先來一道裸題：親戚

問題描述
若某個家族人員過于龐大，要判斷兩個是否是親戚，確實還很不容易，現在給出某個親戚關系圖，求任意給出的兩個人是否具有親戚關系。
規定
x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。

數據輸入：
第一行：三個整數n,m,p，（n<=5000,m<=5000,p<=5000），分別表示有n個人，m個親戚關系，詢問p對親戚關系。
以下m行：每行兩個數Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有親戚關系。
接下來p行：每行兩個數Pi，Pj，詢問Pi和Pj是否具有親戚關系。
數據輸出：
P行，每行一個’Yes’或’No’。表示第i個詢問的答案為“具有”或“不具有”親戚關系
樣例：
input
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
output
Yes
Yes
No

solution：

一題并查集裸題，只是為了演示整體代碼。明顯只是維護集合的合并，詢問結點連通性。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const int INF=0x3f3f3f3f;//1061109567 const int MAXN=20005; /*--------------------------------------------------------------------*/ //請省略以上部分int f[MAXN]; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f; } int find(int x){ return f[x]=(f[x]==x?x:find(f[x])); } void Union(int x,int y) {int xx=find(x),yy=find(y); if (xx!=yy) f[xx]=yy; } void init(int n){ for (int i=1;i<=n;i++) f[i]=i; } int main() {int n=read(),m=read(),Case=read();init(n);for (int i=1;i<=m;i++){int x=read(),y=read();Union(x,y);}while (Case--){int x=read(),y=read();if (find(x)==find(y)) puts("Yes");else puts("No");}return 0; }

2.一道稍稍不同的題：POJ1988 Cube Staking

Description
Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.

• In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
• In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

Input

• Line 1: A single integer, P
• Lines 2…P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a ‘M’ for a move operation or a ‘C’ for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output
Print the output from each of the count operations in the same order as the input file.

Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

Sample Output
1
0
2
Source
USACO 2004 U S Open

Solution

題意：
有兩種操作：

將一堆立方體x堆在另一堆立方體y上面。

詢問x下面有多少個立方體。

這一題需要維護兩個額外的信息：

r[i]表示從i結點到根節點一共有多少結點（i到根的距離+1）

num[i]表示子樹一共有多少結點。

只需要稍稍更改find的過程即可。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const int INF=0x3f3f3f3f;//1061109567 const int MAXN=30005; /*--------------------------------------------------------------------*/ //請省略以上部分int f[MAXN<<1],r[MAXN<<1],num[MAXN<<1]; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f; } inline char readc() {char c=getchar();while (!isalnum(c)) c=getchar();return c; } inline int find(int x) {if (f[x]==x) return x;int tmp=f[x];f[x]=find(f[x]);r[x]+=r[tmp];return f[x]; } int main() {int Case=read();for (int i=1;i<=MAXN;i++) f[i]=i,num[i]=1,r[i]=0;for (int i=1;i<=Case;i++){char c=readc();if (c=='M'){int x=read(),y=read();int xx=find(x),yy=find(y);if (xx!=yy){f[yy]=xx;r[yy]=num[xx];num[xx]+=num[yy];}}else {int x=read();int xx=find(x);printf("%d\n",num[xx]-r[x]-1);}} return 0; }

本文總結

以上是一些并查集的簡單應用，但也是一些精妙并查集技巧操作的基礎。

若已經熟練掌握這些基礎，那么可以學習一些其他更精妙并查集的方法：

并查集的結點刪除

帶權并查集（偏移向量、補集應用 Ps：名字很多 ）

并查集的擴展域

這些內容以后博主會慢慢補充。

總結

以上是生活随笔為你收集整理的并查集（并茶几）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。