?一.定義

定義：
并查集是一種樹型的數據結構，用于處理一些不相交集合的合并及查詢問題（即所謂的并、查）。比如說，我們可以用并查集來判斷一個森林中有幾棵樹、某個節點是否屬于某棵樹等。

主要構成：
并查集主要由一個整型數組pre[ ]和兩個函數find( )、join( )構成。
數組 pre[ ] 記錄了每個點的前驅節點是誰，函數 find(x) 用于查找指定節點 x 屬于哪個集合，函數 join(x,y) 用于合并兩個節點 x 和 y 。

作用：
并查集的主要作用是求連通分支數（如果一個圖中所有點都存在可達關系（直接或間接相連），則此圖的連通分支數為1；如果此圖有兩大子圖各自全部可達，則此圖的連通分支數為2……）

?二.代碼

find( )函數的定義與實現

故事引入：
子夜，小昭于驪山下快馬送信，發現一頭戴竹笠之人立于前方，其形似黑蝠，倒掛于樹前，甚懼，正系拔劍之時，只聽四周悠悠傳來：“如此夜深，姑涼竟敢擅闖明教，何不下坐陪我喝上一盅？”。小昭聽聞，后覺此人乃明教四大護法之一的青翼蝠王韋一笑，答道：“在下小昭，乃紫衫龍王之女”。蝠王輕惕，急問道：“爾等既為龍王之女，故同為明教中人。敢問閣下教主大名，若非本教中人，于明教之地肆意走動那可是死罪！”。小昭嚇得趕緊打了個電話問龍王：“龍王啊，咱教主叫啥名字來著？”，龍王答道：“吾教主乃張無忌也！”，小昭遂答蝠王：“張無忌！”。蝠王聽后，抱拳請禮以讓之。
在上面的情境中，小昭向他的上級（紫衫龍王）請示教主名稱，龍王在得到申請后也向他的上級（張無忌）請示教主名稱，此時由于張無忌就是教主，因此他直接反饋給龍王教主名稱是“張無忌”。同理，青翼蝠王也經歷了這一請示過程。
在并查集中，用于查詢各自的教主名字的函數就是我們的find()函數。find(x)的作用是用于查找某個人所在門派的教主，換言之就是用于對某個給定的點x，返回其所屬集合的代表。

實現：
首先我們需要定義一個數組：int pre[1000]; （數組長度依題意而定）。這個數組記錄了每個人的上級是誰。這些人從0或1開始編號（依題意而定）。比如說pre[16]=6就表示16號的上級是6號。如果一個人的上級就是他自己，那說明他就是教主了，查找到此結束。也有孤家寡人自成一派的，比如歐陽鋒，那么他的上級就是他自己。
每個人都只認自己的上級。比如小昭只知道自己的上級是紫衫龍王。教主是誰？不認識！要想知道自己教主的名稱，只能一級級查上去。因此你可以視find(x)這個函數就是找教主用的。
下面給出這個函數的具體實現：

int find(int x)					//查找x的教主
{while(pre[x] != x)			//如果x的上級不是自己（則說明找到的人不是教主）x = pre[x];				//x繼續找他的上級，直到找到教主為止return x;					//教主駕到~~~
}

?

join( )函數的定義與實現

故事引入：
虛竹和周芷若是我個人非常喜歡的兩個人物，他們的教主分別是玄慈方丈和滅絕師太，但是顯然這兩個人屬于不同門派，但是我又不想看到他們打架。于是，我就去問了下玄慈和滅絕：“你看你們倆都沒頭發，要不就做朋友吧”。他們倆看在我的面子上同意了，這一同意非同小可，它直接換來了少林和峨眉的永世和平。

實現：
在上面的情景中，兩個已存的不同門派就這樣完成了合并。這么重大的變化，要如何實現？要改動多少地方？其實很簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧。這樣一來，兩派原先所有人員的教主就都變成了師太，于是下面的人們也就不會打起來了！反正我們關心的只是連通性，門派內部的結構不要緊的”。玄慈聽后立刻就不樂意了：“我靠，憑什么是我變成她手下呀，怎么不反過來？我抗議！”。抗議無效，我安排的，最大。反正誰加入誰效果是一樣的，我就隨手指定了一個，join()函數的作用就是用來實現這個的。

join(x,y)的執行邏輯如下：
1、尋找 x 的代表元（即教主）；
2、尋找 y 的代表元（即教主）；
3、如果 x 和 y 不相等，則隨便選一個人作為另一個人的上級，如此一來就完成了 x 和 y 的合并。
下面給出這個函數的具體實現：

void join(int x,int y)                     //我想讓虛竹和周芷若做朋友
{int fx=find(x), fy=find(y);            //虛竹的老大是玄慈，芷若MM的老大是滅絕if(fx != fy)                           //玄慈和滅絕顯然不是同一個人pre[fx]=fy;                        //方丈只好委委屈屈地當了師太的手下啦
}

總結

1、用集合中的某個元素來代表這個集合，則該元素稱為此集合的代表元；
2 、一個集合內的所有元素組織成以代表元為根的樹形結構；
3 、對于每一個元素 x，pre[x] 存放 x 在樹形結構中的父親節點（如果 x 是根節點，則令pre[x] = x）；
4 、對于查找操作，假設需要確定 x 所在的的集合，也就是確定集合的代表元。可以沿著pre[x]不斷在樹形結構中向上移動，直到到達根節點。
因此，基于這樣的特性，并查集的主要用途有以下兩點：
1、維護無向圖的連通性（判斷兩個點是否在同一連通塊內，或增加一條邊后是否會產生環）；
2、用在求解最小生成樹的Kruskal算法里。

一般來說，一個并查集對應三個操作：
1、初始化（ Init()函數 ）
2、查找函數（ Find()函數 ）
3、合并集合函數（ Join()函數 ）

#include<bits/stdc++.h>
using  namespace std;
#define int long long
int n,m;
int pre[10007];
void init(){for(int i=1;i<=n;i++){pre[i]=i;//每個結點的上級都是自己 }
}
int find(int x){ //查找結點 x的根結點 if(pre[x]!=x){pre[x]=find(pre[x]);//遞歸出口：x的上級為 x本身，則 x為根結點 }return pre[x];//遞歸查找 
}
void join(int x,int y){int fx=find(x);//尋找 x的代表元int fy=find(y);//尋找 y的代表元if(fx!=fy){//不同集合則合并pre[fx]=fy;}
}
bool isSame(int x,int y){return find(x)==find(y);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;init();while(m--){int num;cin>>num;if(num==1){int x,y;cin>>x>>y;join(x,y);}else{int x,y;cin>>x>>y;if(isSame(x,y)==0){cout<<"N"<<endl;}else{cout<<"Y"<<endl;}}}system("pause");return 0;
}

三.例題一?

?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int pre[10010];
void init(){for(int i=1;i<=n;i++){pre[i]=i;}
}
int find(int x){if(pre[x]!=x){pre[x]=find(pre[x]);}return pre[x];
}
void join(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy){pre[fx]=fy;}
}
bool issame(int x,int y){return find(x)==find(y);
}
int main(){cin>>n>>m>>k;init();while(m--){int a,b;cin>>a>>b;join(a,b);}while(k--){int a,b;cin>>a>>b;if(issame(a,b)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}system("pause");return 0;
}

??

四.例題二 （加反集）

?

?

關于反集

我也是做這道題才知道的

如果a和b是敵人，合并n+b和a，n+a和b

如果c和a是敵人，合并n+c和a，n+a和c

那么b和c就并在一起了

這樣就符合了題目敵人的敵人是朋友的規則

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int pre[10010];
map<int,int> mp;
void init(){for(int i=1;i<=2*n;i++){pre[i]=i;//這里初始化為2*n}
}
int find(int x){if(pre[x]!=x){pre[x]=find(pre[x]);}return pre[x];
}
void join(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy){pre[fx]=fy;}
}
int main(){cin>>n>>k;init();while(k--){string s;cin>>s;int a,b;cin>>a>>b;if(s=="F"){join(a,b);}else if(s=="E"){join(n+a,b);join(n+b,a);}}int cnt=0;for(int i=1;i<=n;i++){if(pre[i]==i) cnt++;}cout<<cnt<<endl;system("pause");return 0;
}

?

?