Kruskal算法和不相交集数据结构：我需要以下两行代码吗？

Question

我已经根据维基百科使用不相交集数据结构在 C++ 中实现了 Kruskal 算法，如下所示：

#include <stdio.h>
#include <algorithm>
#define MAX_EDGES 10000000
#define MAX_VERTICES 200001
using namespace std;
int num_edges,num_vertices;
int total_cost=0;

struct edge{
    int v1,v2;
    int cost;
};

struct comp{
    bool operator()(const edge& e1,const edge& e2){
        return e1.cost<e2.cost;
    }
};

edge edges[MAX_EDGES];
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];

int findset(int x){
    if(x!=parent[x]){
        parent[x]=findset(parent[x]);
    }
    return parent[x];
}

void merge(int x,int y){
    int px=findset(x),py=findset(y);
    if(rank[px]>rank[py]){
        parent[py]=px;
    }else{
        parent[px]=py;
    }
    if(rank[px]==rank[py]){
        ++rank[py];
    }
}

int main(){
    FILE* in=fopen("input","r");
    FILE* out=fopen("output","w");
    fscanf(in,"%d %d\n",&num_vertices,&num_edges);
    for(int i=1;i<=num_vertices;++i){
        parent[i]=i;
        rank[i]=0;
    }
    for(int i=0;i<num_edges;++i){
        fscanf(in,"%d %d %d\n",&edges[i].v1,&edges[i].v2,&edges[i].cost);
    }
    sort(edges,edges+num_edges,comp());
    for(int i=0;i<num_edges;++i){
        int s1=findset(edges[i].v1),s2=findset(edges[i].v2);
        if(s1!=s2){
            merge(s1,s2);
            total_cost+=edges[i].cost;
        }
    }
    fprintf(out,"%d\n",total_cost);
}

我的问题是：我需要这两行代码吗？如果是这样，它们的重要性是什么？

1. int px=findset(x),py=findset(y); 在合并中而不是 int px=parent[x],py=parent[y];
2. parent[x]=findset(parent[x]); 中 findset 而不是 return findset(父[x]);

Answer 1

1) findset(x) 返回 x 所在集合的规范表示（其祖先树的根）。您需要它能够比较两个元素是否在同一集合中（它们具有相同的代表），parent[x] 只是返回树中 x 的父级，这可能不会成为根。

1a) 您忘记在 merge 中测试 px 和 py 是否相同。

2) 这是一种优化，以便将来对 findset 的调用运行得更快。如果 parent[x] 用于指向其父级，而父级又指向其集合树的根，则在调用此调用后，parent[x] 将直接指向根。

Answer 2

1. 您需要这个，因为 x.parent 不一定是 x 所属类的代表，因此如果没有它，算法将不正确。
2. 如果没有分配，算法将不是最优的。这是路径压缩优化，维基百科中也对此进行了讨论。