并集查找中边的顺序重要吗？

Question

我正在学习并查找，为了更好地理解它，我编写了一个小程序：

#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 索引）未连接。我认为这是因为当我们处理边 时{1,3}，顶点1和3尚未连接到更大的组件（它们稍后通过{1,4}），因此并集查找确定它是一个不同的组件。

这是否意味着边的顺序对于 Union find 很重要？或者，我错过了什么吗？

Answer 1

您获得的输出并不表示一个节点已断开连接。

该parent数据结构表示从一个节点到另一个节点（或它本身，当它是根时）的链接。

一开始你有这个：

最后我们有这个：

这里重要的是有一棵树。并不要求所有节点都直接链接到根，只要它们有一条到根的路径即可，对于索引为 3 的节点也是如此。

注意：如果您调用find(3)，那么索引 3 也会收到值 0。这只是通过调用 进行优化的东西find，但它不会改变结果的含义。