我在學習 聯合發現為了更好地理解它，我撰寫了一個小程式：
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
vector<int> parent, sz;
int find(int i) {
if(parent[i]==i) return i;
return parent[i]=find(parent[i]);
}
void merge(int i, int j) {
int p1=find(i);
int p2=find(j);
if(p1==p2) return;
if(sz[p1]<sz[p2]) {
parent[p1]=p2;
sz[p2] =sz[p1];
} else {
parent[p2]=p1;
sz[p1] =sz[p2];
}
}
int main() {
vector<vector<int>> allowedSwaps={{0,4},{4,2},{1,3},{1,4}};
int n=5; //hard-code for now
sz.resize(n,1);
parent.resize(n);
iota(begin(parent),end(parent),0);
cout<<"Parents before: \n";
for(auto& e: parent)
cout<<e<<" ";
cout<<"\n";
for(vector<int>& currswap: allowedSwaps) {
merge(currswap[0],currswap[1]);
}
cout<<"Parents after: \n";
for(auto& e: parent)
cout<<e<<" ";
cout<<"\n";
return 0;
}
allowedSwaps本質上表示所有相互連接的組件。對于上面的代碼，它們都是連接的。
但是，如果您注意到輸出：
Parents before:
0 1 2 3 4
Parents after:
0 0 0 1 0
它表明其中之一 ( 3, 0-indexed) 未連接。我認為這是因為當我們處理 edge 時{1,3}，頂點1和3尚未連接到較大的組件（它們稍后， by {1,4}），因此 Union Find 確定它是不同的組件。
這是否意味著邊的順序對聯合查找很重要？或者，我錯過了什么？
uj5u.com熱心網友回復：
您得到的輸出并不表示一個節點已斷開連接。
parent資料結構表示從一個節點到另一個節點（或自身，當它是根時）的鏈接。
一開始你有這個：
最后我們有這個：
這里重要的是有一棵樹。不需要所有節點都直接鏈接到根，只要它們有到根的路徑即可，對于索引為 3 的節點也是如此。
注意：如果你呼叫find(3)，那么索引 3 也會收到值 0。這只是通過呼叫得到優化的東西find，但它不會改變結果的含義。
uj5u.com熱心網友回復：
直到這一點，我一直在你的問題中與你同在：
Parents after: 0 0 0 1 0它表明其中一個（3, 0-indexed）未連接。
實際上，專案 3 確實與所有其他專案相關聯。想想如果你find(3)在這里打電話會發生什么。由于 3 的父節點是 1，而 1 的父節點是 0，因此我們的呼叫find(3)將回傳 0，即包含其他所有內容的同一個集群。
我認為在這里可能會絆倒你的是兩個元素可以在同一個集群中，即使它們的直系父母不同。這很正常，這就是為什么該find函式會跟蹤父項，直到找到一個屬于它自己的父項的專案。
uj5u.com熱心網友回復：
您正在處理路徑壓縮問題。合并所有連接的組件后，只需find()為每個元素呼叫您的函式。請考慮在程式末尾添加以下行：
for(int i=0; i<5; i =1) find(i);
cout<<"Parents after path compression: \n";
for(auto& e: parent)
cout<<e<<" ";
cout<<"\n";
你會得到這樣的預期結果：
Parents before:
0 1 2 3 4
Parents after:
0 0 0 1 0
Parents after path compression:
0 0 0 0 0
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/410209.html
標籤：
上一篇：查找連接單元的長度為1s