C/C++并查集的查詢與合并實(shí)現(xiàn)原理
標(biāo)題:并查集的查詢與合并詳解 作者:@Ggggggtm 寄語:與其忙著訴苦,不如低頭趕路,奮路前行,終將遇到一番好風(fēng)景
一、并查集的概念
并查集是一種樹形的數(shù)據(jù)結(jié)構(gòu)。使用樹型結(jié)構(gòu)來存儲數(shù)據(jù)。樹根的編號即為整個樹的標(biāo)號,且每個節(jié)點(diǎn)存儲的數(shù)據(jù)是他的父節(jié)點(diǎn)下標(biāo)。
并查集被很多OIer認(rèn)為是最簡潔而優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)之一,主要用于解決一些元素分組的問題。它管理一系列不相交的集合,并支持兩種操作:
- 合并(Union):把兩個不相交的集合合并為一個集合。
- 查詢(Find):查詢兩個元素是否在同一個集合中。
二、并查集的實(shí)現(xiàn)
1.并查集不同集合(樹)的形成
我們把并查集不同集合(樹)的實(shí)現(xiàn)主要分為以下幾個點(diǎn):
- 我們先給出n個數(shù)據(jù),把n個數(shù)據(jù)存儲到不同的集合當(dāng)中(p[ i ] = i),在這里我們把每個p[ i ]分別看成一個不同集合(也就是一棵樹)。
- p[ i ] = i,i即為這棵樹的編號,這顆樹下面的孩子節(jié)點(diǎn)存儲的數(shù)據(jù)是父節(jié)點(diǎn)的下標(biāo)。
- 當(dāng)p[ i]=i 時,就相當(dāng)于找到了根節(jié)點(diǎn)。
- 我們剛開始每個集合中的元素只有一個。后續(xù)合并后,集合元素個數(shù)不斷增加。
2.find()函數(shù)找一個元素集合的編號
(元素所屬于樹的祖宗)
我們查找一個元素的集合,把元素的當(dāng)作下標(biāo)傳給find()函數(shù),代碼如下:
int find(int x) { if(p[x]!=x) { p[x]=find(p[x]); } return p[x]; }
我們p[x]中存儲的正是他的父節(jié)點(diǎn),從而就可以一直往上查找,直到p[ x ]=x時結(jié)束。當(dāng)p[ x ]=x時,就相當(dāng)于找到了根節(jié)點(diǎn)。此時的p[ x ]存儲的是這棵樹的編號。我這發(fā)現(xiàn),剛開始每個集合當(dāng)中都只有一個元素,也就是p[ x ],后面我們會對不同的集合進(jìn)行合并,使得一個集合有多個元素。
我們再找祖宗節(jié)點(diǎn)時進(jìn)行了路徑壓縮。什么是路徑壓縮呢?路徑壓縮就是我們在查找某個元素的祖宗時,在找父節(jié)點(diǎn)的這條路經(jīng)上的元素都指向祖宗節(jié)點(diǎn),以便于我們后面的查找的時間復(fù)雜度近乎O(1)。
3.合并兩個不同集合(合并兩棵不同的樹)
我們直到了每棵樹的根節(jié)點(diǎn)存儲的是這個樹的編號,而不是父節(jié)點(diǎn)。當(dāng)我們要合并兩顆樹時,我們只需要把一棵樹的根節(jié)點(diǎn)存儲的編號改為另一棵樹的根節(jié)點(diǎn)編號。簡單的理解就是一個樹的根節(jié)不再是根節(jié)點(diǎn),而是一個子節(jié)點(diǎn),該樹的根節(jié)點(diǎn)存儲的也不再是編號,而是存儲的父節(jié)點(diǎn),該父節(jié)點(diǎn)就是另一棵樹的根節(jié)點(diǎn)。我們看代碼:
//合并 把a(bǔ)的祖宗節(jié)點(diǎn)的父節(jié)點(diǎn)當(dāng)作b的祖宗結(jié)點(diǎn) p[find(a)]=find(b);
4.查詢兩個元素是否在一個集合
我們有了find()函數(shù),就可以很簡單的判斷出兩個元素的是否在同一個集合當(dāng)中(兩個元素是否在同一個樹中)。我們只需要判斷兩個元素集合的編號是否相同(兩個元素的祖宗節(jié)點(diǎn)是否相同)即可。我們看代碼:
//看a、b兩個元素是否在同一個集合當(dāng)中 if(find(a)==find(b)) cout<<"Yes"<<endl; else cout<<"No"<<endl;
5.并查集例題訓(xùn)練1
一共有 n 個數(shù),編號是1∼n,最開始每個數(shù)各自在一個集合中。
現(xiàn)在要進(jìn)行m個操作,操作共有兩種:
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≤10e5 1≤n,m≤10e5
輸入樣例:
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() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) p[i]=i; while(m--) { char op[2]; int a,b; cin>>op>>a>>b; if(op[0]=='M') { //合并 把a(bǔ)的祖宗節(jié)點(diǎn)的父節(jié)點(diǎn)當(dāng)作b的祖宗結(jié)點(diǎn) p[find(a)]=find(b); } else { if(find(a)==find(b)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
6.并查集例題訓(xùn)練2
給定一個包含nn個點(diǎn)(編號為1∼n1∼n)的無向圖,初始時圖中沒有邊。
現(xiàn)在要進(jìn)行mm個操作,操作共有三種:
C a b
,在點(diǎn)aa和點(diǎn)bb之間連一條邊,aa和bb可能相等;Q1 a b
,詢問點(diǎn)aa和點(diǎn)bb是否在同一個連通塊中,aa和bb可能相等;Q2 a
,詢問點(diǎn)aa所在連通塊中點(diǎn)的數(shù)量;
輸入格式
第一行輸入整數(shù)nn和mm。
接下來mm行,每行包含一個操作指令,指令為C a b
,Q1 a b
或Q2 a
中的一種。
輸出格式
對于每個詢問指令Q1 a b
,如果aa和bb在同一個連通塊中,則輸出Yes
,否則輸出No
。
對于每個詢問指令Q2 a
,輸出一個整數(shù)表示點(diǎn)aa所在連通塊中點(diǎn)的數(shù)量
每個結(jié)果占一行。
數(shù)據(jù)范圍
1≤n,m≤1051≤n,m≤105
輸入樣例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
輸出樣例:
Yes
2
3
我們這個題相對于上個題就是對出了一個統(tǒng)計(jì)一個集合元素的個數(shù)。整體思路大同小異,我們直接看代碼解析:
#include<iostream> using namespace std; const int N=100010; int p[N],cnt[N]; int find(int x) { if(p[x]!=x) { p[x]=find(p[x]); } return p[x]; } int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++) { p[i]=i; cnt[i]=1; } while(m--) { char op[5]; int a,b; scanf("%s",op); if(op[0]=='C') { scanf("%d%d",&a,&b); if(find(a)==find(b)) continue; cnt[find(b)]+=cnt[find(a)]; p[find(a)]=find(b); } else if(op[1]=='1') { scanf("%d%d",&a,&b); if(find(a)==find(b)) printf("Yes\n"); else printf("No\n"); } else { scanf("%d",&a); printf("%d\n",cnt[find(a)]); } } return 0; }
注意,我們剛開始每個集合中的元素只有一個。后續(xù)合并后,集合元素個數(shù)不斷增加。
三、總結(jié)
我們主要掌握find()函數(shù),并查集算法中,最為核心的就是find()函數(shù)。在這個算法中,路徑壓縮給我們的算法效率提高了很多,這個也是需要理解的。合并、查詢是并查集的兩個主要操作,我們也應(yīng)該熟悉理解。
到此這篇關(guān)于C/C++并查集的查詢與合并實(shí)現(xiàn)原理的文章就介紹到這了,更多相關(guān)C++并查集內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
win10環(huán)境下C++ vs2015編譯opencv249的教程
這篇文章主要介紹了win10環(huán)境下C++ vs2015編譯opencv249的教程,本文分步驟給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03C++使用CriticalSection實(shí)現(xiàn)線程同步實(shí)例
這篇文章主要介紹了C++使用CriticalSection實(shí)現(xiàn)線程同步實(shí)例,是使用CriticalSection對前文實(shí)例的擴(kuò)展,具有一定的參考借鑒價值,需要的朋友可以參考下2014-10-10