c++ - 边的顺序在 union 查找中重要吗？

Question

我在学习union-find为了更好地理解它，我写了一个 small程序:

#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)未连接。我认为这是因为当我们处理边 {1,3} 时，顶点 1 和 3 都没有连接到较大的组件(它们是稍后的，由 {1,4})，因此 Union Find 确定它是一个不同的组件。

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

Answer 1

你得到的输出并不表示有一个节点断开了。

parent 数据结构表示从一个节点到另一个节点(或自身，当它是根时)的链接。

一开始你有这个:

最后我们得到了这个:

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

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