並查集

語言: CN / TW / HK

並查集學習知識點 

·並查集概念

·並查集的基礎操作:初始化、合併與查詢

·並查集優化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-SetUnion-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,也就是如下這個關係: 

對於單個點A 1 ,我們可以給它建兩個虛點A 2 ,A 3 ,並且假設出這三個點之間的關係,A 1 吃 A 2, A 2 吃 A 3 ,A 3 吃A 1 。同樣在假設有一個點B 1 ,它同樣也有這些虛點。我們可以使用一個有向圖來表示這個關係以方便理解。

當A 1 可以吃掉B 1 時,我們可以發現A 1 和 B 3 成了同類(參考定理 1,同樣根據定理 1,我們還可以得出A 2 和B 1 是同類,如果是B 1 吃A 1 則相反)。

根據定理 2,我們可以得出B 1 可以吃掉A 3 ,同時它也可以吃掉B 2 ,所以A 3 和 B 2 也是同類..

如果我們判斷兩個點是同類,則可以將他們放入同一個並查集中。需要注意的是,虛點只是用來幫助我們判斷動物之間的關係的,並沒有實際含義。

那麼如何判斷一句話是矛盾的呢,我們可以分情況討論。 如果A 1 可以吃B 1 ,結合圖片,我們可以發現A 1 和B 2 ,依此類推 B 1 和A 3 也不是同類,A 1 和 B 1 更不是同類。我們便可以使用並查集,如果上述兩者在同一個並查集,便說明它們是矛盾的。

同理如果A 1 和B 1 是同類的話也可以這麼考慮。需要注意的是,所以情況都要考慮完,實點和虛點入並查集時情況也要考慮完(不然就是 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;
}

參考: 【演算法與資料結構】—— 並查集