問題描述
問題輸入是一對整數對，每個整數都代表一個物件，一對整數”p,q“表示 ”p與q相連“（具有自反性，傳遞性，對稱性，被歸到一個等價類里），要求撰寫程式來篩除在輸入時就已經在一個等價類里的整數對，這個演算法可以在計算機網路連結方面發揮作用：每個整數相當于計算機，整數對相當于網路間的連結，我們的程式可以判斷為了使p，q兩個計算機連結，需不需要添加一個新的線路，
具體思想
1.根節點判斷
我們可以通過一個“概念上”的森林來實作我們的程式，我們把union-find演算法打包成一個類，在其中設定一個名為id的陣列用來存放每個節點的下一個連結物件，這樣可以通過接受一個陣列的秩來不斷訪問它所連結的下一個物件，直至到一個秩和所存盤物件節點號相同的節點（根節點），而比較兩個節點的根節點就可以判斷他們是否連在同一個根節點上，進而判斷出兩個節點是否已經連結，
2.加權連結
如果判斷兩個節點沒有連結到一個根節點，我們就對他們的根節點進行連結，這時就會產生一個問題：p去連q還是q去連p，這里我們采用加權的演算法：引入一個陣列sz（size）來記錄每個節點作為根節點時樹中的節點數，把它作為節點的權值，每次進行根節點連結時，我們總是把權值小的根節點連結到權值大的根節點上，這樣的好處是可以極大地降低樹的高度的增加速度（最大程度降速的方式是把樹高度作為權值的加權連結，但經過路徑壓縮后，這種方式變得沒有必要），從而降低查找根節點時的時間量級，在最壞的情況下，要連結的樹的大小總是相等的，且都是2的冪，則把所有的N個節點合成一個樹，這個樹的高度是底數為2的N的對數，
致使查找要檢索的高度也達到O(logN)，
PS:本圖取自Algorithm(4th)中譯版P146（原版P229）
實作代碼
#include<iostream>
#include<vector>
#include<random>
using namespace std;
//WeightedQuickUnion(加權快速連結)
class WQU {
vector<int> id;
vector<int> sz;
int count = 0;
int numberOfSite = 0;
public:
int find(int p);
void Union(int p, int q);
int get_count() { return count; }
bool connected(int p, int q);
int Count(int n);
int newSite();
};
bool WQU::connected(int p, int q) {
if (p >= numberOfSite || q >= numberOfSite) {
throw runtime_error("Site does not exist");
}
return find(p) == find(q);
}
//壓縮路徑find，遞回，只修改查找時經歷節點的連結
int WQU::find(int p) {
if (p >= numberOfSite) {
throw runtime_error("Site does not exist");
}
if (p == id[p]) { return p; }
return id[p] = find(id[p]);
}
void WQU::Union(int p, int q) {
if (p >= numberOfSite || q >= numberOfSite) {
throw runtime_error("Site does not exist");
}
int rp = find(p);
int rq = find(q);
if (rp == rq) { return; }
if (sz[rp] < sz[rq]) {
id[rp] = rq;
sz[rq] += sz[rp];
}
else {
id[rq] = rp;
sz[rp] += sz[rq];
}
--count;
}
//測驗隨機生成資料最終連在一棵樹上所需的連結條數
int WQU::Count(int n) {
while (n > numberOfSite) { newSite(); }
while (get_count() != 1) {
int p = rand() % n;
int q = rand() % n;
cout << p << ' ' << q << endl;
if (!connected(p, q)) {
Union(p, q);
}
}
int cnt = 0;
for (size_t i = 0; i < id.size(); ++i) {
if (i != id[i]) {
++cnt;
}
}
return cnt;
}
//創建一個參與連結的新節點，回傳它的值
int WQU::newSite() {
id.push_back(numberOfSite);
sz.push_back(1);
++count;
return numberOfSite++;
}
int main() {
int n;
cin >> n;
WQU temp;
cout << temp.Count(n);
return 0;
}
find采用遞回壓縮路徑，在不改變根節點的情況下，令被查找過的節點指向其根節點，從而降低被查找過的節點的深度，進而降低再次查找時的時間復雜度，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282230.html
標籤：其他
上一篇：[畢設] 用Rust實作一個3D渲染器 - 淺談MSAA抗鋸齒
下一篇：高速車路協同新基建論壇后感