目錄
并查集是什么？
舉個例子
組成
父親數組：
find函數：
union函數：
代碼實現：
fa[] 初始化code:
find code：
遞歸實現:
非遞歸實現:
union code :
畫圖模擬：
路徑壓縮：
路徑壓縮Code：
并查集是什么？
是一種樹形的數據結構，一般用來處理集合的合并，查詢操作。
舉個例子
告訴你1的父節點是2 2的父節點是3 4的父節點是5 6沒有父節點 那么可以畫出
三個集合，或者說是樹?。然后我們一般用并查集判斷：①有幾棵樹 也就是有幾個集合 ② 兩個點是否同屬于一個集合 ③一個點是不是屬于這棵樹?
組成
主要是通過一個父親數組和一個find函數、一個union函數實現的。
父親數組：
記錄一個節點的父結點 初始化為自己 也就是一開始自己就是自己的父結點 自己單獨屬于一個集合
find函數：
根據鄰接關系 找到一個結點的根結點 如果兩個結點的通過find函數尋找出來的結點相同 則同屬一個集合
union函數：
遍歷鄰接關系時 將兩個鄰接的結點父親數組更新的作用 具體來說 判斷若兩個結點通過find函數尋找出來的根節點不相同 也就是不屬于一個集合 則將一個集合并入另一個集合 通過把前一個結點的根節點 的父親數組 標記為第二個結點的根節點 則兩個集合就合并了
代碼實現：
fa[] 初始化code:
for(int i=0;i<n;++i)fa[i]=i;find code：
遞歸實現:
int finds(int a){if(a!=fa[a]){fa[a]=finds(fa[a]);}return fa[a];
}非遞歸實現:
int finds(int a){while(a!=fa[a]){a=fa[a];}return fa[a];
}詳細解釋：一個結點 只有父結點是自己 也就是fa[]數組中是自己 才能稱為根節點 finds函數就是判斷一個結點是否為根結點?如果不是 就繼續向上finds他的父節點 看是不是根結點 直到找到根節點 返回 這個根節點可以稱之為一個集合的標志
union code :
void unions(int x,int y){int fx=finds(x);int fy=finds(y);if(fx!=fy){fa[fx]=fy;}
}詳細解釋：unions函數是用于遍歷鄰接關系時 更新集合關系。傳入兩個結點 找到他們的根節點 也就是他們所屬集合的標志 判斷是否相同 也就是判斷是否從屬于一個集合 如果不屬于一個集合 則把第一個集合的根節點 的父親結點 更新為?第二個集合的根節點。也就是把第一個集合和第二個集合合并 并且根節點保留為第二個集合的根節點 。
畫圖模擬：
①我們要判斷兩個點是否屬于一個集合 只要用find函數即可?
②我們要判斷共有幾個集合 只要看fa數組中有幾個 i=fa[i]即可 因為fa[i]等于i 代表是集合里的根結點 一個集合只有一個根結點 所以根結點數即為集合數量
路徑壓縮：
可以觀察到 每次調用find函數都需要經歷一串長長的遞歸 這正是函數時間花費的地方 考慮優化的地方 我們可以直接把fa[i]數組標記為i結點所屬集合的根節點 也就是把整條路徑上的fa[i]數組都標記為根節點 按上面畫圖的例題來說 就是把fa[1] fa[3] fa[4] 全部標記為4 這樣調用find函數的時候就特別快，一步到位。要想完成這個操作 只要在find函數后加一步 每次find的時候 找到了根節點的值 保存 再用一個while循環向上查找 把整條路徑上的結點的fa[]值都更新為找到的根節點?
路徑壓縮Code：
int new_finds(int a){int aa=a;//保存一下查找的點 也就是路徑的底部if(a!=fa[a]){fa[a]=finds(fa[a]);//找到了根節點}while(aa!=fa[a]){//向上更新整條路徑int temp=fa[aa];//先存儲路徑的下一個點fa[aa]=fa[a];//路徑壓縮一個aa=temp;//再壓縮下一個點}return fa[a];
}
)
