一：并查集的相關知識

這道題用到了并查集，所以我就學了一下并查集，所以把自己的見解也分享給大家（建議 先看視頻 再瀏覽 博客 再自己敲一遍 學習效率高而已，我總是亂著來 以為看幾篇博客就會了，其實最后還是老老實實 去B站看大佬講解視頻 才搞懂）

1:并查集

并查集是一種樹型的數據結構，
用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題
1：查詢元素a和元素b是否屬于同一組
2：合并元素a和元素b所在組 （將有相同元素的元素 合并為一個組 ）
3：需要初始化一個數組存放父節點，其索引值 代表元素

2：并查集的AC代碼（模板`）

/*并查集是一種樹型的數據結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題1：查詢元素a和元素b是否屬于同一組2：合并元素a和元素b所在組 （將有相同元素的元素 合并為一個組 ） 3：需要初始化一個數組存放父節點，其索引值 代表元素 */#include<bits/stdc++.h> using namespace std;int father[100]; int find( int x){while( x != father[x] ){x = father[x];}return x; } void merge(int x,int y) {int a = find(x);//x的根節點為a int b = find(y);//y的根節點為bif( a != b )father[b] = a;//那么將b的根節點 設為 a }int main() {//初始化： 我們將每一個結點的前導結點設置為自己，//如果在merge函數時未能形成連通，將獨立成點for( int i = 0; i < 10; i++ ){father[i] = i;}}

上方的find函數 效率不高，當處理大數據時，使用并查集查找時，如果查找次數很多，那么使用樸素版的查找方式肯定要超時。比如，有一百萬個元素，每次都從第一百萬個開始找，這樣一次運算就是10^{6，如果程序要求查找個一千萬次，這樣下來就是10}13,肯定要出問題的。

所以有了壓縮路徑的算法（就是一棵樹只有葉節點）

int find( int a ){int r=a;while(Father[r]!=r)r=Father[r]; //找到他的前導結點int i=a,j;while(i!=r){ //路徑壓縮算法j=Father[i]; //記錄x的前導結點Father[i]=r; //將i的前導結點設置為r根節點i=j;}return r; }

如有疑問 請留言！ 加油陌生的你

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的并查集的相关知识详解 Come baby!!!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。