一、概念：

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢(xún)問(wèn)題。

并查集的思想是用一個(gè)數(shù)組表示了整片森林（parent），樹(shù)的根節(jié)點(diǎn)唯一標(biāo)識(shí)了一個(gè)集合

我們只要找到了某個(gè)元素的的樹(shù)根，就能確定它在哪個(gè)集合里。

二、用法：

并查集用在一些有 N 個(gè)元素的集合應(yīng)用問(wèn)題中，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。

這個(gè)過(guò)程看似并不復(fù)雜，但數(shù)據(jù)量極大，若用其他的數(shù)據(jù)結(jié)構(gòu)來(lái)描述的話(huà)，往往在空間上過(guò)大，計(jì)算機(jī)無(wú)法承受，也無(wú)法在短時(shí)間內(nèi)計(jì)算出結(jié)果，所以只能用并查集來(lái)處理。

簡(jiǎn)述一下：

1，將兩個(gè)集合合并。

2，詢(xún)問(wèn)兩個(gè)集合是否在同一集合中。

三、基本原理：

每個(gè)集合用一顆樹(shù)來(lái)儲(chǔ)存。樹(shù)的根節(jié)點(diǎn)編號(hào)是每個(gè)集合的編號(hào)。

每個(gè)節(jié)點(diǎn)存儲(chǔ)它的父節(jié)點(diǎn)，p[x]表示x的父節(jié)點(diǎn)。

四、常見(jiàn)問(wèn)題/要處理的問(wèn)題：

1，如何判斷樹(shù)根：if(p[x]==x)

2，如何求x的集合編號(hào)： while(p[x]!=x) x=p[x] (對(duì)照用法二)

3，如何合并兩個(gè)集合：px是x的集合邊界，py是y的編號(hào)集合。p[x]=y

實(shí)踐題目：

一共有 n 個(gè)數(shù)，編號(hào)是 1∼n，最開(kāi)始每個(gè)數(shù)各自在一個(gè)集合中。

現(xiàn)在要進(jìn)行 mm 個(gè)操作，操作共有兩種：

• M a b ，將編號(hào)為 a 和 b 的兩個(gè)數(shù)所在的集合合并，如果兩個(gè)數(shù)已經(jīng)在同一個(gè)集合中，則忽略這個(gè)操作；
• Q a b ，詢(xún)問(wèn)編號(hào)為 a 和 b 的兩個(gè)數(shù)是否在同一個(gè)集合中；

輸入格式

第一行輸入整數(shù) n 和 m。

接下來(lái) m 行，每行包含一個(gè)操作指令，指令為  M a b  或  Q a b  中的一種。

輸出格式

對(duì)于每個(gè)詢(xún)問(wèn)指令  Q a b ，都要輸出一個(gè)結(jié)果，如果 a 和 b 在同一集合內(nèi)，則輸出  Yes ，否則輸出  No 。

每個(gè)結(jié)果占一行。

數(shù)據(jù)范圍

1≤n,m≤10^5   

1≤n,m≤10^5

輸入樣例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

輸出樣例：

Yes
No
Yes

先上代碼：

#include<iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int x){
	if(p[x]!=x){
		p[x]=find(p[x]);
	}
	return p[x];
}
int main(){
	char op[2];
	int n,i,j,k,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	while(m--){
		int a,b;
		cin>>op>>a>>b;
		if(op[0]=='M'){
			p[find(a)]=find(b);
		}
		else{
			if(find(a)==find(b)){
				cout<<"Yes"<<endl;
			}
			else{
				cout<<"No"<<endl;
			}
		}
	}
	return 0;	
}

解讀思路：

初始化：由于一開(kāi)始我們得到的是幾個(gè)散亂的集合，即每個(gè)數(shù)都是一個(gè)集合，所以我們初始化為 p[x]=x ，這就表示他自己就是一個(gè)集合，也可以說(shuō)成他就是自己的父節(jié)點(diǎn)/祖宗節(jié)點(diǎn)。

集合合并與查找：假如我們有{1}，{2}這兩個(gè)單獨(dú)集合,我們要把它合成一個(gè)集合，就需要把他們的祖宗節(jié)點(diǎn)變成一個(gè)，就是上面說(shuō)到的 p[x]=p[y]=x

注：這里以誰(shuí)為父節(jié)點(diǎn)是按你輸入的順序定的馬，可以理解為隨機(jī)的，例如你第一個(gè)數(shù)是1，那么之后的想要把其他數(shù)都合并在1這個(gè)數(shù)的集合里，那么他們的父節(jié)點(diǎn)為 p[1]=p[2]=p[3]=....p[n]=1 ）之后集合就成了{(lán)1 , 2}。

那么我們的查找操作也相應(yīng)完成了，既然都在一個(gè)集合里，都有一個(gè)父節(jié)點(diǎn)，判斷兩個(gè)數(shù)是否在一個(gè)集合里直接比較父節(jié)點(diǎn)即可，高效準(zhǔn)確。

find()函數(shù)：這里建議自己模擬一遍。如果此時(shí)我們已經(jīng)將1，2合并到一個(gè)集合中去，此時(shí)把1再執(zhí)行一邊f(xié)ind函數(shù)，根據(jù)代碼：p[1]=2 -> !=1 -> p[1]=find(2) -> p[2]=2 -> return 2  結(jié)束函數(shù)。

好，我們加一問(wèn)，詢(xún)問(wèn)某個(gè)數(shù)所在集合中的元素?cái)?shù)量。

代碼：

#include<iostream>
using namespace std;
const int N = 100010;
int p[N];
int siz[N];
int find(int x){
	if(p[x]!=x){
		p[x]=find(p[x]);
	}
	return p[x];
}
int main(){
	char op[2];
	int n,i,j,k,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
		size[i]=1;
	}
	while(m--){
		int a,b;
		cin>>op;
		if(op[1]=='1'){
			cin>>a>>b;
			if(find(a)==find(b)){
				cout<<"Yes"<<endl;
			}
			else{
				cout<<"No"<<endl;
			}
		}
		else if(op[0]=='C'){
			cin>>a>>b;
			if(find(a)==find(b)){
				continue;//注意特判，否則重復(fù)相加個(gè)數(shù)
			}
			siz[find(b)]+=siz[find(a)];
			p[find(a)]=find(b);
		}
		else{
			cin>>a;
			cout<<siz[find(a)]<<endl;
		}
	}
	return 0;	
}

思路大致相同，要找某個(gè)數(shù)所在集合中元素的個(gè)數(shù)，我們也只需找到他的父節(jié)點(diǎn)的標(biāo)號(hào)下的元素個(gè)數(shù)即可。

我們需要開(kāi)一個(gè)size[]數(shù)組存放元素個(gè)數(shù)，例如還是舉上面的例子：1，2，3在同一個(gè)集合里，他們的父節(jié)點(diǎn)是p[2]=2，那么他們的size的值也都變成size[2]=size[3]=size[1]=3，另外這個(gè)數(shù)組也是需要維護(hù)更新的

我們看具體操作：先初始化，size[i]=1，之后相加即可。

為什么siz[]里面的參數(shù)是find(x)呢，原因還是要找到相同的父節(jié)點(diǎn)。

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之并查集詳解的文章就介紹到這了,更多相關(guān)C++并查集內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論