一、概念：

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

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

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

二、用法：

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

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

簡述一下：

1，將兩個集合合并。

2，詢問兩個集合是否在同一集合中。

三、基本原理：

每個集合用一顆樹來儲存。樹的根節(jié)點編號是每個集合的編號。

每個節(jié)點存儲它的父節(jié)點，p[x]表示x的父節(jié)點。

四、常見問題/要處理的問題：

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

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

3，如何合并兩個集合：px是x的集合邊界，py是y的編號集合。p[x]=y

實踐題目：

一共有 n 個數(shù)，編號是 1∼n，最開始每個數(shù)各自在一個集合中。

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

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

輸入格式

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

接下來 m 行，每行包含一個操作指令，指令為  M a b  或  Q a b  中的一種。

輸出格式

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

每個結(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;	
}

解讀思路：

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

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

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

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

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

好，我們加一問，詢問某個數(shù)所在集合中的元素數(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ù)相加個數(shù)
			}
			siz[find(b)]+=siz[find(a)];
			p[find(a)]=find(b);
		}
		else{
			cin>>a;
			cout<<siz[find(a)]<<endl;
		}
	}
	return 0;	
}

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

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

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

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

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

最新評論