带路径压缩算法的加权快速联合-联合查找

Question

我有一个项目，我必须实现一个带有路径压缩算法的加权快速并集。在看到其他一些源代码后，我最终得到了这个：

public class UnionFind {

private int[] parent;
private int[] size;
private int maxItemCount;      // maximum number of items from {0,1,...,N-1}
private int numItems;      // number of items created

UnionFind(int N) {
    this.N = N;
    this.K = 0;
    parent = new int[N];
    size = new int[N];
    for (int i = 0; i < N; i++) {
        parent[i] = -1;
        size[i] = 0;
    }
}

void makeSet(int v) {
    if (parent[v] != -1) return; // item v already belongs in a set
    parent[v] = v;
    size[v] = 1;
    K++;
}

int find(int v) {
    if (v == parent[v]) {
        return v;
    }
       return parent[v] = find(parent[v]);
    }


void unite(int v, int u) {
    int x=find(v);
    int y=find(u);
    if(x!=y) {
        parent[x]=y;
    }
}

int setCount() {
    int item=0;
    for(int i=0;i<parent.length;i++) {
        if(i==parent[i]) {
            item++;
        }
    }
    return item; // change appropriately 
}

int itemCount() {
    return K;
}

分配给我的任务是正确完成以下方法:

1. int find（int v）
2. void unite（int v，int u）
3. setCount（int v）

嗯，算法似乎很慢，我找不到合适的解决方案。

Answer 1

以下是一些问题：

>

未使用大小信息，但该信息对于保持所需的性能至关重要。最重要的是，团结起来：

• 大小应保持更新：联合集的成员数与两个给定集的成员数目相同
• ＜code＞size＜/code＞应该确定两个根节点中的哪一个应该是联合集的根，因为这将保持树的平衡

设置计数具有 O（n） 时间复杂度。它可以在O（1）时间内提供信息，如果你要在成员变量中跟踪这个数字。我称之为数字集。如果 setCount（） 被调用很多，则此更改将产生积极的影响。

没问题，但是将变量命名为N和K无助于使代码具有可读性。为什么不给它们真正说明它们是什么的名称，这样您就不需要在它们的定义中附上注释来给出解释了？

以下是经过修改的代码:

public class UnionFind {
    
    private int[] parent;
    private int[] size;
    private int maxItemCount;
    private int numItems;
    private int numSets;
    
    UnionFind(int maxItemCount) {
        this.maxItemCount = maxItemCount;
        numItems = 0;
        numSets = 0;
        parent = new int[maxItemCount];
        size = new int[maxItemCount];
        for (int i = 0; i < maxItemCount; i++) {
            parent[i] = -1;
            size[i] = 0;
        }
    }
    
    void makeSet(int v) {
        if (parent[v] != -1) return; // item v already belongs in a set
        parent[v] = v;
        size[v] = 1;
        numItems++;
        numSets++;  // Keep track of number of sets
    }
    
    int find(int v) {
        if (v == parent[v]) {
            return v;
        }
        return parent[v] = find(parent[v]);
    }
    
    void unite(int v, int u) {
        int x = find(v);
        int y = find(u);
        if (x != y) {
            numSets--; // A union decreases the set count
            // Determine which node becomes the root
            if (size[x] < size[y]) {
                parent[x] = y;
                size[y] += size[x]; // Adapt size
            } else {
                parent[y] = x;
                size[x] += size[y]; // Adapt size
            }
        }
    }
    
    int setCount() {
        return numSets; // Kept track of it
    }
    
    int itemCount() {
        return numItems;
    }
}