c++并查集知識(shí)點(diǎn)有哪些

這篇文章主要介紹“c++并查集知識(shí)點(diǎn)有哪些”，在日常操作中，相信很多人在c++并查集知識(shí)點(diǎn)有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對(duì)大家解答”c++并查集知識(shí)點(diǎn)有哪些”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

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

有一個(gè)聯(lián)合- 查找算法定義了兩個(gè)用于此數(shù)據(jù)結(jié)構(gòu)的操作：

Find ：確定元素屬于哪一個(gè)子集。它可以被用來確定兩個(gè)元素是否屬于同一子集。  Union：將兩個(gè)子集合并成同一個(gè)集合。

并查集主要運(yùn)用在合并元素以及查詢兩個(gè)元素是否在同一集合的問題，在信息學(xué)競賽中廣泛涉及

初始化：

一開始，每一個(gè)元素都是一個(gè)集合，打個(gè)比方，每個(gè)人所在的 "家族" 只有他一個(gè)人。我們還需要一個(gè)f 數(shù)組，里面存的是他的 “父親” 的編號(hào)，初始值為f[1]=1,f[2]=2……f[n]=n，如圖

2、find函數(shù)：find（a）是用來查找a的“祖先”的，例如，我們要查找 a的祖先，就要去找a 的父親的父親……，直到有個(gè)人 b，他的父親就是他自己，那么 b就是 a的祖先代碼如下：int find (int x){  if(f[x] == x) return x;//如果x的父親就是他自己，則x為a的祖先else return find (f[x]);//否則a的祖先 就是a的父親的祖先}int x=find(a);find函數(shù)：find（a）是用來查找a的“祖先”的，例如，我們要查找 a的祖先，就要去找a 的父親的父親……，直到有個(gè)人 b，他的父親就是他自己，那么 b就是 a的祖先代碼如下：int find (int x){  if(f[x] == x) return x;//如果x的父親就是他自己，則x為a的祖先else return find (f[x]);//否則a的祖先 就是a的父親的祖先}int x=find(a);

union函數(shù)：

union(a,b)就是合并 a,b這兩個(gè)人所在的家族，只需要把 a的祖先的父親 指向 b的祖先

如何合并？我們?cè)O(shè)u=find(a),v=find(b) , 只要將 u,v其中一個(gè)人的父親編號(hào)指向另外一個(gè)人就行了，例如f[u]=v

代碼如下：

void Union (int a,int b)//因?yàn)閡nion是c++的保留字，所以只好大寫u{  int u= find(a), v= find(b);//尋找a，b的祖先  f[u]=v;//合并家族}Union (a,b);

在合并的時(shí)候還有一個(gè)注意點(diǎn)：為什么不能直接把 a的父親指向 b？因?yàn)檫@樣并不能合并完全，a的父親，a 的父親的父親……，都不能合并到b 的家族里（想一想，為什么？），如圖

5、查詢兩個(gè)元素是否在同一集合里：查詢 a,b是否在同一集合里，就是看他們的祖先是否相等，若相等則在同一集合里，否則就不在代碼如下：if( find(a) == find(b) ) cout<<"Y\n"; //如果祖先相等就輸出“Y”else cout<<"N\n"; //否則輸出“N”查詢兩個(gè)元素是否在同一集合里：查詢 a,b是否在同一集合里，就是看他們的祖先是否相等，若相等則在同一集合里，否則就不在代碼如下：if( find(a) == find(b) ) cout<<"Y\n"; //如果祖先相等就輸出“Y”else cout<<"N\n"; //否則輸出“N”

例題：

至此，你應(yīng)該對(duì)并查集有了初步的了解，是時(shí)候上例題了

題目描述

如題，現(xiàn)在有一個(gè)并查集，你需要完成合并和查詢操作。

輸入輸出格式

輸入格式：

第一行包含兩個(gè)整數(shù)N、M，表示共有N個(gè)元素和M個(gè)操作。

接下來M行，每行包含三個(gè)整數(shù)Zi、Xi、Yi

當(dāng)Zi=1時(shí)，將Xi與Yi所在的集合合并

當(dāng)Zi=2時(shí)，輸出Xi與Yi是否在同一集合內(nèi)，是的話輸出Y；否則話輸出N

輸出格式：

如上，對(duì)于每一個(gè)Zi=2的操作，都有一行輸出，每行包含一個(gè)大寫字母，為Y或者N

其實(shí)，這道題目就是把上面幾個(gè)步驟綜合在一起，代碼如下

并查集的路徑壓縮

路徑壓縮，顧名思義，就是將本來要很多步完成的事情壓縮成一步

因?yàn)槲覀兠看蝔ind(a) 都要消耗 O (a的層數(shù)) 的時(shí)間，如果數(shù)據(jù)構(gòu)造成一條鏈，則每次find 都需要O(n) 的時(shí)間，這是我們不希望看到的

所以，我們可以把 f 數(shù)組的性質(zhì)改變一下 f[a] 指向的編號(hào)變?yōu)閍 的祖先

代碼該怎么寫呢？我們只需要在 find 函數(shù)里把

return find (f[x]);

變成

return f[x]=find(f[x]);

就可以了

這樣每一次find 都會(huì)使路徑上的每個(gè)f[x] 指向x 的祖先，每一次 find 也就只需要1 步就行了（除非被合并過，那也只需要 2 步），這就是路徑壓縮的實(shí)質(zhì)

到此，關(guān)于“c++并查集知識(shí)點(diǎn)有哪些”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！