c++初級并查集知識點總結(jié)

更新時間：2019年07月08日 14:17:34 作者：Alex___Wei

在本篇文章里小編給各位分享的是關(guān)于c++初級并查集知識點以及實例代碼內(nèi)容，有需要的朋友們學(xué)習(xí)下。

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

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

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

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

初始化：

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

2、find函數(shù)：find（a）是用來查找a的“祖先”的，例如，我們要查找 a 的祖先，就要去找 a 的父親的父親……，直到有個人 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 的父親的父親……，直到有個人 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 這兩個人所在的家族，只需要把 a的祖先的父親指向 b的祖先

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

代碼如下：

void Union (int a,int b)//因為union是c++的保留字，所以只好大寫u

{

  int u= find(a), v= find(b);//尋找a，b的祖先

  f[u]=v;//合并家族

}

Union (a,b);

在合并的時候還有一個注意點：為什么不能直接把 a 的父親指向 b ？因為這樣并不能合并完全，a 的父親， a 的父親的父親……，都不能合并到 b 的家族里（想一想，為什么？），如圖

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

例題：

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

題目描述

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

輸入輸出格式

輸入格式：

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

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

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

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

輸出格式：

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