0

我的代码试图实现联合查找算法，我有 id[] 数组和 sz[] 数组。我在 Union-Find 构造函数中初始化它们，但是一旦我尝试在 Union-Find 类的方法中使用这些数组，它会将所有数组值更改为 1。我不明白为什么。我有什么明显的遗漏吗？

文件

class UnionFind{
public:
    UnionFind(int size);
    void join(int x, int y);
    int connected(int x, int y);
    int find(int x);

private:

    int size;
    int id[];
    int sz[];

};

CPP 文件

UnionFind::UnionFind(int size){
        this->id[size] = id[size];
        for(int i = 0; i < size; i++){
            id[i] = i;
        }
        for(int i = 0; i < size; i++){
            sz[i] = 1;
        }
    }

    int UnionFind::find(int l){
        //Path Compression Finding the Root
        for(int i = 0; i < 5; i++){
        }
        while(l != id[l]){
            id[l] = id[id[l]];
            l = id[l];
        }
        return l;

    }

    void UnionFind::join(int x, int y){
        int m = find(x);
        int n = find(y);

        if(sz[m] < sz[n]){
            id[m] = n;
            sz[n] += sz[m];
        }
        else{
            id[n] = m;
            sz[m] += sz[n];
        }
    }

    int UnionFind::connected(int x, int y){
        if(find(x) == find(y)){
            return 1;
        }
        else{
            return 0;
        }
    }
4

1 回答 1

2

从评论。

  • 你不能int id[]作为班级成员，
  • 使用std::vector（调整大小并填写构造函数），
  • 你忘了size在构造函数中设置成员，
  • 您的查找算法使用路径减半而不是路径压缩（这不会影响运行时间）。

旁注：您可以使用单个数组/向量来实现不相交的集合数据结构。

于 2015-01-19T21:59:30.767 回答