c++ - 如何在C++中的不交集中合并路径压缩？

Question

我有这个用-1值初始化的DisjointSets类。我想在find()中实现路径压缩，以便在find()完成运行后，元素i及其在上级树中的所有祖先都指向根。我怎样才能做到这一点？

class DisjointSets {
public:
    int s[256];

    DisjointSets() { for (int i = 0; i < 256; i++) s[i] = -1; }
    int find(int i);
};

int DisjointSets::find(int i) {
  if ( s[i] < 0 ) {
    return i;
  }
  else {
    return find(s[i]);
  }
}

主要功能测试代码:

int main() {
  DisjointSets d;

  d.s[1] = 3;
  d.s[3] = 5;
  d.s[5] = 7;
  d.s[7] = -1;

  std::cout << "d.find(3) = " << d.find(3) << std::endl;
  std::cout << "d.s(1) = " << d.s[1] << std::endl;
  std::cout << "d.s(3) = " << d.s[3] << std::endl;
  std::cout << "d.s(5) = " << d.s[5] << std::endl;
  std::cout << "d.s(7) = " << d.s[7] << std::endl;

  return 0;
}

基本上，在上面的示例中，值1指向3，3指向5，5指向7，直到7指向-1。当值指向-1时，即是上树中设置的不相交的根或标识，即7是根。 1、3、5是7的祖先。

Answer 1

您可以递归执行

function Find(x)
   if x.parent != x
     x.parent := Find(x.parent)
   return x.parent

在您的情况下，一个非常基本的实现可能是

struct subset
{
    int parent;
    int rank;
};

int findSet(std::vector<subset>&s, int x)
{
    if(s[x].parent != x) 
        s[x].parent = findSet(s, s[x].parent);

    return s[x].parent;
}