首先，我們可以聽一個故事，
有許多的村莊，其實都是由一個人發展出來的，有些時候，我們想要知道兩個人是不是一個村莊的，只要知道他的爸爸是哪個村莊的，這就是查找，
有一天，一個村莊的長老對另一個村莊的長老說：“欸，你們這個村莊就和我們一起吧！”但是我們知道，如果一個村子有兩位長老肯定是會出問題的，所以我們可以試著讓一個長老的所有人成為另一個長老的兒子，這樣就可以讓一個村莊合并到另一個里面了，這就是合并，
但可惜的是，如果村莊中某個人想脫離關系，這樣做會讓關于他的所有人都脫離關系，所以長老不允許這樣做，
現在試想，如果使用二維陣列（或者MAP）做這個事你會發現：
如果你嘗試合并兩個大村莊時，要改變長老的人太多，改不過來了！
我們試著修改一下合并的方法，發現其實直接把一個村莊的長老改了就好，因為其他人都是屬于長老的，長老怎么變其他人就怎么變（而具體找長老的辦法可以下翻），
可這時，很容易發現，如果一個村莊的人只有1個，但是另一個有很多很多人，要是把人多的那個村莊合并到小村莊太劃不來了，所以我們決定把小村莊合并到大村莊
而這樣的代價是我們需要一個陣列來存盤自己的人數或者深度，但是在很多時候可以為我們優化掉很高的時間復雜度，
接著再來看看查找，我們的第一個辦法是在每一個人出生的時候就記住長老是哪個，
可是我們發現，如果出現了二代（即父親不一定是長老），再用我們的方法就不好了，因為每次有孩子出現都要去找長老問他是誰，
所以我們可以直接把陣列換成存盤父親，這樣每次有孩子出現只需要存父親，這樣子依然可以找到祖先（若假如孩子是第 \(N\) 代，遞回時間復雜度為 \(O(n)\) ），
但是這樣做我們又會發現，害，我爸爸要知道誰是長老要弄一次，我要知道誰是長老還要再弄一次，這不白忙活嗎，我只要讓我爸爸永遠記住自己家長老是誰，后來我直接讓父親告訴我不行嗎？
這個辦法好，因為我們發現我家長老是誰跟我父親是誰沒有任何關系啊，所以我們可以一次使用終生受益，（若假設上一輩為 \(N\) 代）時間復雜度在第一次查找時有 \(O(n)\) ，但是對于 \(1,2\cdots ,N-1\) 代來說找祖先只有 \(O(1)\) 的復雜度（直接讀取不就行了嗎），
所以我們設計了一種資料結構叫做并查集，而我們最優的那種查找辦法叫做路徑壓縮，最優的合并方法則叫按秩合并（但需要注意的是，所有人父親一開是必須是自己），R.E.Tarjan在1984年的論文中證明了所有情況下并查集的最壞時間情況：
很容易發現在僅使用路徑壓縮的情況下時間復雜度有\(O(m \ log \ n)\)以及其他情況下的時間復雜度，
現在我們來嘗試一下實作這個事情，
按照我們的合并方式，可以假設用了一個陣列 \(d\) 存盤深度或者點數（兒子的個數），用陣列 \(f\) 表示自己的父親，這樣很容易得到一種C++實作法：
void union(int x,int y){
if(d[x]<=d[y]){
f[find(x)]=find(y);//y比x人多或者一樣多，就需要把x歸屬到y那里，
}
else if(d[x]>d[y]){
f[find(y)]=find(x);//x比y人多，就需要把y歸屬到x那里，
}
}
這里的 \(find\) 函式則需要使用到我們的路徑壓縮，
int find(x){
if(x!=f[x]){//初始化的時候，長老的爸爸必須是自己，
x=find(f[x]);//通過遞回找長老，在回傳值的時候可以直接路徑壓縮，
}
return f[x];
}
這樣我們就擁有了一個完整的并查集資料結構了，
拓展研究
關于怎么樣在并查集刪點這回事，（這部分純屬蒟蒻瞎想，歡迎diss）
首先最基本的問題就是我們不能夠使用路徑壓縮了，因為路徑壓縮旨在不管中間的人怎么樣，我和長老好就對了，但是目前的問題在于不一定我和長老中間的人沒事，所以蒟蒻個人認為不能夠使用路徑壓縮法，只能每個人都暴力遞回找長老了，
我們不能夠很簡單地洗掉點，但是本蒟蒻認為，可以通過bool陣列記錄解決問題，如果是其他型別的還可以用MAP記錄是否被洗掉，
記錄后，如果在找點時路遇洗掉點，本蒟蒻認為可以回傳特殊值，而這個特殊值可以表示斷路的意思，這樣在回傳時仍然可以做小小的優化，如這個點的值是表示斷路的，可以直接認為這是個斷路，不必再向長老找，
推薦習題
你谷P3367
你谷P1551
你谷P3367
完
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/278732.html
標籤：C++