并查集學習知識點
·并查集概念
·并查集的基礎操作：初始化、合并與查詢
·并查集優化1：路徑壓縮
·并查集優化2：按秩合并(啟發式合并)
·帶權并查集
·種類并查集
引入：
??話說在江湖中散落著各式各樣的大俠，他們懷揣著各自的理想和信仰在江湖中奔波，或是追求武林至尊，或是遠離紅塵，或是居廟堂之高，或是處江湖之遠，盡管大多數人都安分地在做自己，但總有些人會因為彼此的信仰不同而聚眾斗毆，因此，江湖上常年亂作一團，紛紛擾擾，
這樣長期的混戰，難免會打錯人，說不定一刀就把擁有和自己相同信仰的隊友給殺了，這該如何是好呢？于是，那些有著相同信仰的人們便聚在一起，進而形成了各種各樣的門派，比如我們所熟知的“華山派”、“峨嵋派”、“,崆峒派”、“少林寺”、“明教”……這樣一來，那些有著相同信仰的人們便聚在一起成為了朋友，以后再遇到要打架的事時，就不會打錯人了，
??但是新的問題又來了，原本互不相識的兩個人如何辨別是否共屬同一門派呢?
這好辦！我們可以先在門派中選舉一個“大哥”作為話事人（也就是掌門人，或稱教主等），這樣一來，每當要打架的時候，決斗雙方先自報家門，說出自己所在門派的教主名稱，如果名稱相同，就說明是自己人，就不必自相殘殺了，否則才能進行決斗，于是，教主下令將整個門派劃分為三六九等，使得整個門派內部形成一個嚴格的等級制度（即樹形結構），教主就是根節點，下面分別是二級、三級、……、N級隊員，每個人只需要記住自己的上級名稱，以后遇到需要辨別敵友的情況時，只需要一層層往上詢問就能知道是否是同道中人了，
資料結構的角度來看：
??由于我們的重點是在關注兩個人是否連通，因此他們具體是如何連通的，內部結構是怎樣的，甚至根節點是哪個（即教主是誰），都不重要，所以并查集在初始化時，教主可以隨意選擇（就不必再搞什么武林大會了），只要能分清敵友關系就行，
??備注：上面所說的“教主”在教材中被稱為“代表元”，
即：用集合中的某個元素來代表這個集合，則該元素稱為此集合的代表元，
??什么是并查集？
??在一些有N個元素的集合應用問題中，我們通常是在開始時讓每個元素構成一個單元素的集合，然后按一定順序將屬于同一組的元素所在的集合合并，其間要反復查找一個元素在哪個集合中，這一類問題近幾年來反復出現在資訊學的國際國內競賽題中，其特點是看似并不復雜，但資料量極大，若用正常的資料結構來描述的話，往往超過了空間的限制，計算機無法承受；即使在空間上能勉強通過，運行的時間復雜度也極高，根本不可能在比賽規定的運行時間內計算出試題需要的結果，只能采用一種特殊資料結構——并查集來描述，
·舉一個例子
設初始有若干元素：1,2,3,4,5,6,7,8
元素之間有若干關系：1~3,2~4,5~6,3~5,7~8,4~8
關系合并程序：
??初始 {1},{2},{3},{4},{5},{6},{7},{8}
??1~3：{1,3},{2},{4},{5},{6},{7},{8}
??2~4：{1,3},{2,4},{5},{6},{7},{8}
??5~6：{1,3},{2,4},{5,6},{7},{8}
??3~5：{1,3,5,6},{2,4},{7},{8}
??7~8：{1,3,5,6},{2,4},{7,8}
??4~8：{1,3,5,6},{2,4,7,8}
并查集概念
??并查集(Disjoint-Set或Union-Find Set)是一種表示不相交集合的資料結構，用于處理不相交集合的合并與查詢問題，在不相交集合中，每個集合通過代表來區分，代表是集合中的某個成員，能夠起到唯一標識該集合的作用，一般來說，選擇哪一個元素作為代表是無關緊要的，關鍵是在進行查找操作時，得到的答案是一致的(通常把并查集資料結構構造成樹形結構，根節點即為代表)， 在不相交集合上，需要經常進行如下操作:
·findSet(x):查找元素 x 屬于哪個集合，如果 x 屬于某一集合，則回傳該集合的代表，
·unionSet(x，y):如果元素 x 和元素 y 分別屬于不同的集合，則將兩個集合合并，否則不做操作，
并查集的實作方法是使用有根樹來表示集合——樹中的每個結點都表示集合的一個元素，每棵樹表示一個集合，每棵樹的根結點作為該集合的代表，
并查集基礎操作：初始化
??現共有N個元素，對這N個元素要進行查詢與合并操作，現進行初始化；例如N = 10，初始化方法如下，father[i]為i的父結點編號，初始化時結點的父結點為本身，即自己代表自己，建立N個獨立集合：
void MakeSet(int n) {
for (int i = 1; i <= n; i++)
father[i] = i;
}并查集基礎操作：查詢
故事引入：
??子夜，小昭于驪山下快馬送信，發現一頭戴竹笠之人立于前方，其形似黑蝠，倒掛于樹前，甚懼，正系拔劍之時，只聽四周悠悠傳來：“如此夜深，姑涼竟敢擅闖明教，何不下坐陪我喝上一盅？”，小昭聽聞，后覺此人乃明教四大護法之一的青翼蝠王韋一笑，答道：“在下小昭，乃紫衫龍王之女”，蝠王輕惕，急問道：“爾等既為龍王之女，故同為明教中人，敢問閣下教主大名，若非本教中人，于明教之地肆意走動那可是死罪！”，小昭嚇得趕緊打了個電話問龍王：“龍王啊，咱教主叫啥名字來著？”，龍王答道：“吾教主乃張無忌也！”，小昭遂答蝠王：“張無忌！”，蝠王聽后，抱拳請禮以讓之，
??在上面的情境中，小昭向他的上級（紫衫龍王）請示教主名稱，龍王在得到申請后也向他的上級（張無忌）請示教主名稱，此時由于張無忌就是教主，因此他直接反饋給龍王教主名稱是“張無忌”，同理，青翼蝠王也經歷了這一請示程序，
在并查集中，用于查詢各自的教主名字的函式就是我們的find()函式，find(x)的作用是用于查找某個人所在門派的教主，換言之就是用于對某個給定的點x，回傳其所屬集合的代表，
實作：
??首先我們需要定義一個陣列：int pre[1000]; （陣列長度依題意而定），這個陣列記錄了每個人的上級是誰，這些人從0或1開始編號（依題意而定），比如說pre[16]=6就表示16號的上級是6號，如果一個人的上級就是他自己，那說明他就是教主了，查找到此結束，也有孤家寡人自成一派的，比如歐陽鋒，那么他的上級就是他自己，
??每個人都只認自己的上級，比如小昭只知道自己的上級是紫衫龍王，教主是誰？不認識！要想知道自己教主的名稱，只能一級級查上去，因此你可以視find(x)這個函式就是找教主用的，
??查詢操作是遞回查詢，在查詢某個結點在哪一個集合中時，需沿著其父結點，遞回向上，因所屬集合代表指向的仍然是其本身，所以可以以father[x] == x作為遞回查詢出口，
int FindSet(int x) {
if (father[x] == x) return x;
else return FindSet(father[x]);
}?例如要查詢3所在的集合，只需要沿著3的父結點 向上，一直到一個自己指向自己的結點，該結點 就是這個3結點所屬集合的代表，為2，
并查集基礎操作：合并
故事引入：
??虛竹和周芷若是我個人非常喜歡的兩個人物，他們的教主分別是玄慈方丈和滅絕師太，但是顯然這兩個人屬于不同門派，但是我又不想看到他們打架，于是，我就去問了下玄慈和滅絕：“你看你們倆都沒頭發，要不就做朋友吧”，他們倆看在我的面子上同意了，這一同意非同小可，它直接換來了少林和峨眉的永世和平，
實作：
??在上面的情景中，兩個已存的不同門派就這樣完成了合并，這么重大的變化，要如何實作？要改動多少地方？其實很簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧，這樣一來，兩派原先所有人員的教主就都變成了師太，于是下面的人們也就不會打起來了！反正我們關心的只是連通性，門派內部的結構不要緊的”，玄慈聽后立刻就不樂意了：“憑什么是我變成她手下呀，怎么不反過來？我抗議！”，抗議無效，我安排的，最大，反正誰加入誰效果是一樣的，我就隨手指定了一個，Union()函式的作用就是用來實作這個的，
在進行集合的合并時，只需將兩個集合的代表進行連接即可，即一個代表作為另一個代表的父結點，
Union(x,y)的執行邏輯如下：
1、尋找 x 的代表元（即教主）；
2、尋找 y 的代表元（即教主）；
3、如果 x 和 y 不相等，則隨便選一個人作為另一個人的上級，如此一來就完成了 x 和 y 的合并，
下面給出這個函式的具體實作：
void UnionSet(int x, int y) {
father[FindSet(x)] = FindSet(y);
}
并查集優化1：路徑壓縮
問題引入：
??前面介紹的 Union(x,y) 實際上為我們提供了一個將不同節點進行合并的方法，通常情況下，我們可以結合著回圈來將給定的大量資料合并成為若干個更大的集合（即并查集），但是問題也隨之產生，我們來看這段代碼：
if(fx != fy)
fa[fx]=fy;
??這里并沒有明確誰是誰的前驅（上級）的規則，而是我直接指定后面的資料作為前面資料的前驅（上級），那么這樣就導致了最終的樹狀結構無法預計，即有可能是良好的 n 叉樹，也有可能是單支樹結構（一字長蛇形），試想，如果最后真的形成單支樹結構，那么它的效率就會及其低下（樹的深度過深，那么查詢程序就必然耗時），
而我們最理想的情況就是所有人的直接上級都是教主，這樣一來整個樹的結構就只有兩級，此時查詢教主只需要一次，因此，這就產生了路徑壓縮演算法，
設想這樣一個場景：兩個互不相識的大將夏侯惇和許褚碰面了，他們都互相看不慣，想揍對方，于是按照江湖規矩，先打電話問自己的上級：“你是不是教主？” 上級說：“我不是呀，我的上級是***，我幫你問一下，” 就這樣兩個人一路問下去，直到最終發現他們的教主都是曹操，具體結構如下：
??這樣一來，在剛才查詢程序中涉及到的人物就都聚集在了曹操的直接領導下，以后再需要查詢教主名稱的時候，就只需要詢問一級便可得到，所以，在經過一次查詢后，整個門派樹的高度都將大大降低，路徑壓縮所實作的功能就是這么個意思，
??對于一個集合中的結點，只需要關心它的根結點是誰，不必知道各結點之間的關系(對樹的形態不關心)，希望每個元素到根結點的路徑盡可能短，最好只需要一步，把剛才的樹轉換為右圖中的樹，極大地提高了查詢效率.路徑壓縮需要在查詢操作時，把沿途的每個結點的父節點都設為根結點即可，下一次再查詢時，就可以節約很多時間，
int FindSet(int x) {
if (father[x] == x) return x;
else return father[x] = FindSet(father[x]);
}并查集優化2：按秩合并(啟發式合并)
??由于路徑壓縮只在查詢時進行，每次查詢也只壓縮一條路徑，所以并查集最終的結構仍然可能是比較復雜，例如，現在我們有一棵較復雜的樹需要與一個單結點的集合合并， 如果把7的父節點設為8，會使樹的深度加深，原來樹中每個元素到根結點的距離都變長了，而把8的父結點設為7，則不會有這個問題，因為它沒有影響到不相關的結點，
??這啟發我們：應該把深度低的樹往深度高的樹上合并，用rank陣列記錄根結點對應樹的深度(如果不是根節點，其rank相當于以它作為根節點的子樹的深度)，一開始，把所有元素的rank（秩）設為1，合并時比較兩個根結點，把rank較小者往較大者上合并
//按秩合并初始化
void MakeSet(int n) {
for (int i = 1; i <= n; i++)
father[i] = i, rank[i] = 1;
}//按秩合并
void UnionSet(int x, int y) {
int a = FindSet(x), b = FindSet(y);
if (a == b) return;
if (rank[a] <= rank[b]) father[a] = b;
else father[b] = a;
if (rank[a] == rank[b]) rank[b]++;
}帶權并查集(邊帶權并查集)
并查集實際上是若干棵樹構成的森林，我們可以在樹中的每條邊上記錄一個權值，即維護一個陣列d，用d[x]保存節點x到父節點fa[x]之間的邊權，在每次路徑壓縮后，每個訪問過的節點都會直接指向樹根，如果我們同時更新這些節點的d值，就可以利用路徑壓縮程序來統計每個節點到樹根之間的路徑上的一些資訊，這就是所謂“邊帶權”的并查集，
??eg.銀河英雄傳說
??分析：一條“鏈”也是一棵樹，只不過是樹的特殊形態，因此可以把每一列戰艦看作一個集合，用并查集維護，最初，N個戰艦構成N個獨立的集合， 在沒有路徑壓縮的情況下，fa[x]就表示排在第x號戰艦前面的那個戰艦的編號，一個集合的代表就是位于最前邊的那艘戰艦，另外，讓樹上每條邊權值為1，這樣樹上兩點之間的距離減1就是二者之間間隔的戰艦數量，
??在考慮路徑壓縮的情況下，我們額外建立一個陣列d，d[x]記錄戰艦x與fa[x]之間的邊權，在路徑壓縮把x指向樹根的同時，累加更新d[x]，如下代碼，
int Find(int x) {
if(x==fa[x]) return x;
int root=Find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
}??當接收到一個M x y指令時，把x的樹根作為y的樹根的子節點，連接在一起后，由于題意是x鏈接在y鏈后面(但實際形態不是鏈)，所以y鏈中所有點p到fa[p]的邊權不改變，而x鏈根節點rootx的邊權要改變成y鏈中所有邊數+1，即y鏈中所有節點數，最后y鏈的節點總數size[y]要累加x鏈的節點總數，代碼如下，
fa[x]=y;
d[x]+=Size[y];
Size[y]+=Size[x];
Code
#include<bits/stdc++.h>
using namespace std;
int n,fa[30005],Size[30005],d[30005];
int read(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return rv*fh;
}
int Find(int x)
{
if(x==fa[x])
return x;
int root=Find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=root;
}
int main()
{
for(int i=1;i<=30000;i++) {
fa[i]=i;
Size[i]=1;
d[i]=0;
}
char c;
int a,b,x,y;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf(" %c ",&c);
scanf("%d%d",&a,&b);
x=Find(a),y=Find(b);
if(c=='M')
{
fa[x]=y;
d[x]+=Size[y];
Size[y]+=Size[x];
}
else{
if(x!=y) printf("-1\n");
else {
if(a==b){
printf("0\n");
}
else{
printf("%d\n",abs(d[a]-d[b])-1);
}
}
}
}
return 0;
}種類并查集(擴展域并查集)
??一般的并查集，維護的是具有連通性、傳遞性的關系，例如親戚的親戚是親戚，但有時候要維護另一種關系：敵人的敵人是朋友，種類并查集就是為了解決這個問題，
??我們開一個兩倍大小的并查集，例如，假如我們要維護4個元素的并查集，我們改為開8個單位的空間，藍色集合存盤朋友關系，紅色集合存盤敵人關系，即5存盤1元素的敵人關系，6存盤2元素敵人關系…… 例如(1, 2)是敵人，(2, 4)是敵人.
??eg.[BOI2003]團伙
Code
#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[15000];
int vis[15000];
int find(int x){
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
void un(int x, int y){
int xx = find(x);
int yy = find(y);
if(xx != yy) p[yy] = xx;
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= 2*n; i++)
p[i] = i;
for(int i = 1; i <= m; i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(a == 0) un(b,c);
if(a == 1)
{
un(b+n,c);
un(b,c+n);
}
}
int cnt = 0;
for(int i = 1; i <= n; i++)
{
int t =find(i);
if(!vis[t])
{
vis[t] = 1;
cnt++;
}
}
printf("%d",cnt);
return 0;
}??eg2.食物鏈
??首先考慮題目中所說的 3 種矛盾情況中的后兩種，都很好判斷，關鍵是如何判斷當前的話是與前面的話沖突的，
??這里我們先給出兩個定理以方便判斷一些關系：
一，因為三個種族都有一個且且僅有一個能吃的種族，如果動物 A 能吃 B，動物 C 也能吃 B，那么說明A 和 C 便是同一個種族，否則這個關系就是矛盾的， 二，如果 A 能吃 B，B 能吃 C，那么可以得出 C 能吃 A，也就是如下這個關系：
??對于單個點A1，我們可以給它建兩個虛點A2,A3，并且假設出這三個點之間的關系，A1吃 A2，A2吃 A3，A3吃A1，同樣在假設有一個點B1，它同樣也有這些虛點，我們可以使用一個有向圖來表示這個關系以方便理解，
當A1可以吃掉B1 時，我們可以發現A1和 B3 成了同類（參考定理 1，同樣根據定理 1，我們還可以得出A2和B1是同類，如果是B1吃A1則相反），
根據定理 2，我們可以得出B1可以吃掉A3，同時它也可以吃掉B2，所以A3 和 B2 也是同類..
如果我們判斷兩個點是同類，則可以將他們放入同一個并查集中，需要注意的是，虛點只是用來幫助我們判斷動物之間的關系的，并沒有實際含義，
那么如何判斷一句話是矛盾的呢，我們可以分情況討論， 如果A1 可以吃B1 ，結合圖片，我們可以發現A1和B2，依此類推 B1 和A3也不是同類，A1和 B1更不是同類，我們便可以使用并查集，如果上述兩者在同一個并查集，便說明它們是矛盾的，
同理如果A1 和B1是同類的話也可以這么考慮，需要注意的是，所以情況都要考慮完，實點和虛點入并查集時情況也要考慮完（不然就是 WA,XD），
可能有些同學要問為什么要判斷兩個點在同一個并查集，來判斷這句話是不是矛盾的，而不是判斷兩個點不在同一個并查集，也就是
if(find(A1) == find(B2)） 矛盾和
if(find(A3) != find(B2)) 矛盾的區別，
因為我們建立的是虛點，一開始所有的點都在獨立的并查集，直接判斷便會誤判， 可以這么理解，我們在條件不夠的情況下，第二種方式是 “猜測”，第一種方式則是 “盡量滿足關系，最后不得不判斷矛盾”，
關于建立虛點，設當前有 n 個實點，A的兩個虛點可以用 A+n和 A+2*n來表示.
??
Code
#include<bits/stdc++.h>
using namespace std;
int fa[50005*3],n,k,ans;
int find(int x) {
if(fa[x]!=x) return fa[x]=find(fa[x]);
return x;
}
int main() {
cin>>n>>k;
for(int i=1;i<=n*3;i++) fa[i]=i;
for(int i=1,a,x,y;i<=k;i++) {
scanf("%d%d%d",&a,&x,&y);
if(x>n || y>n || (a==2 && x==y)) { ans++; continue; }
if(a==1) {
if((find(x+n) == find(y)) ||(find(x+2*n) == find(y)))
ans++;
else {
fa[find(x+2*n)]=find(y+2*n);
fa[find(x+n)]=find(y+n);
fa[find(x)]=find(y);
}
}
if(a==2) {
if(find(x)==find(y)||find(x+n*2)==find(y)||find(y+n)==find(x)) ans++;
else {
fa[find(x+n)]=find(y);
fa[find(x)]=find(y+2*n);
fa[find(y+n)]=find(x+2*n);
}
}
}
printf("%d",ans);
return 0;
}
參考：【演算法與資料結構】—— 并查集
本文來自博客園，作者：Doria_tt，轉載請注明原文鏈接：https://www.cnblogs.com/pangtuan666/p/16527300.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/500402.html
標籤：其他