并查集

并查集是用來管理元素分組情況的資料結構。

并查集可以高效的進行如下操作。

查詢元素a和元素b是否屬于同一組。

合并元素a和元素b所在的組。

并查集不能進行分割操作。

并查集的實作就是三個函數

初始化

合并

查尋

在樹形結構中都存在退化的現象，為了讓并查集避免退化我們記錄了樹的高度，在合并的時候我們将高度低的樹加入到高度高的樹上。

我們還用了路徑壓縮（好厲害的名字） 其實就是

從圖中可以很清晰的看明白。

現在我們來寫構造并查集的代碼

第一個初始化：

就是将所有的點都是 自己屬于一類，與别人沒有關系 ，自己的父節點是自己；

接下來是查找函數

查找的是自己最上面的節點是誰，也就是說，自己屬于哪一類；

最後我們來附上最牛掰的 合并函數：

好了  到這我們的并查集就基本結束了。

好了感謝自己堅持