Инициализация переполнения стека массивов

Мой код пытается реализовать алгоритм поиска объединения, и у меня есть массив id [] и массив sz []. Я инициализирую их в конструкторе Union-Find, но как только я пытаюсь использовать эти массивы в методах класса Union-Find, он меняет все значения массива на 1. Я не понимаю, почему. Есть что-то очевидное, что мне не хватает ??

H-файл

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;
}
}

0

Решение

Из комментариев.

  • ты не можешь иметь int id[] как ученик,
  • использование std::vector (изменить размер и заполнить конструктор),
  • Вы забыли установить член size в конструкторе,
  • Ваш алгоритм поиска использует деление пути вдвое, а не сжатие пути (это не влияет на время выполнения).

Примечание: вы можете использовать один массив / вектор для реализации структуры данных вашего несвязанного множества.

2

Другие решения


По вопросам рекламы [email protected]