在一張圖中，我們常常會遇到判斷兩個點是否在同一個連通塊上，此時，我們若采用樸素而低效的dfs的方法，就有超時的危險，于是我們引入了一種更加實用的演算法——并查集，
父節點表示法
首先，我們來了解一個樹的存盤方法：父節點表示法，
因為每個節點只有唯一父節點，于是我們用 parent[i] 來表示節點 \(i\) 的父節點，特別地，我們規定在此時根節點的父節點是其本身，
比如下面這棵樹：
用父節點表示法表示出來就是
tree[2]=2
tree[4]=2
tree[8]=4
tree[6]=4
tree[9]=2
并查集的原理
有了父節點表示，我們就可以開始搞定并查集了，
模板題
首先，我們的并查集一開始是一個森林，每個節點獨立作為一棵樹，
接著，我們來進行合并操作，我們先來合并 \(0,1\) 兩個節點，于是我們把節點 \(0\) 連到 \(1\) 上，就變成了下面這樣：
用代碼表示就是tree[0]=1
但如果我們要合并的兩個節點不是根節點呢？
這個簡單，我們只要向上找到根節點，再合并根節點就行了，
接著進行查詢，我們依然查詢 \(0,1\) 兩個節點，這時只需要一直向上查找至根節點，看兩個根節點是否相同就行了，
如何找根節點呢，我們在上面提到過，根節點的父節點等于本身，于是我們就可以寫出這樣的代碼，
int find_root(int u){
return parent[u]==u?find_root(parent[u]):u;
}
優化
我們看到，對于一個并查集，如果我們的合并使其退化成一條鏈或近似于鏈的狀態會使效率大幅降低，于是需要一定方法優化，
首先，我們想會使效率降低的原因，主要是因為需要一個個找，這讓我們想到類似找LCA的倍增的做法，但與此同時又會讓合并的時間復雜度劇增，因為每次合并都相當于要做一次dfs，
似乎沒啥好方法了？
這時候一個非常機智的想法出現了：路徑壓縮，
我們知道，我們在做并查集的時候并不關心到底這棵樹是怎樣的，我們只要保證合并完了以后兩棵樹確實在一起就行了，
于是我們想到，既然我們不關心樹的結構，那我們把樹破壞掉唄，反正是找根節點，那我們干脆在 find_root() 的時候，直接將子節點連到根節點上去，并且把沿途的節點也連接到根節點上去，于是我們的find_root就可以這么寫了
int find_root(int u){
return parent[u]==u?parent[u]=find_root(parent[u]):u;
}
在這種情況下，單次查詢的時間復雜度為\(O(\log n)\)
最后，附上模板題AC代碼
#include<iostream>
#include<cstring>
using namespace std;
int parent[200000];
int root(int i){
if(parent[i]==i){return i;}
return parent[i]=root(parent[i]);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;++i)parent[i]=i;
int x,a,b;
for(int i=0;i<m;++i){
cin>>x>>a>>b;
if(x==1)parent[root(a)]=root(b);
if(x==2){
if(root(a)==root(b))cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/277285.html
標籤：其他
下一篇：#pragma pack使用方法