我正在尝试解决类似的联合发现问题
即使我发现很少的解决方案和文章来解释如何使用Union-Find来完成此操作，我也无法直观地看到它的工作方式。
例如:Delete(X)可以通过Union(X,X+1)完成，但是它如何充当删除我只是无法看到。与查找Successor(X)相似。
任何帮助/指导或解释的详细说明将大有帮助。
最佳答案
首先，假设列表中有10个数字(从0到9)。
0 1 2 3 4 5 6 7 8 9
就像在常规加权联合查找中一样，这些数字中的每一个都是数组索引，并且数组索引值的内容表示数组索引的父级。
因此，最初，0的父代为0，而0的根(祖 parent 中的最祖 parent )也为0。所有数字都相同。
现在，我们删除一个数字，例如5。
删除5意味着我们实际上是在说联合(5，6)。
因此，这正在发生。
在此阶段，如果我们想找到数字x的后继者，我们可以简单地将其找到为根(x + 1)。因此，4的后继是6，因为根(4 + 1)是6。
现在，假设我们删除了6，这意味着并集(6，7)。
这很棘手，因为在加权联合查找中，由于6-5分量的权重更大，因此应将7(7)的根添加到6(6)的根。但是，如果这样做，我们将如何找到继任者？因为这会发生:
因此，如果要4的后继者，则不能说它是根(4 + 1)，因为根(5)是6，但是6已被删除。 4的后继应该是7。
因此，我们可以使用另一个数组，例如actualList。 此数组将存储需要在列表中的实际数字-对应于任何已删除数字的根。为此，需要对union()进行一行修改。
在这种情况下，actualList数组将存储与索引root(5)和root(6)对应的7。因此，actualList [root(4 + 1)]将得出4的后继者为7的正确答案。
要找到后继者，我们必须访问actualList [(root(x + 1)]而不是root(x + 1)。
这是我在Java中的整个实现:
public class SuccessorWithDelete {
private int id[];
private int sz[];
private int actualList[];
private int N;
public SuccessorWithDelete(int N){
this.N = N;
id = new int[N];
sz = new int[N];
actualList = new int[N];
for(int i=0; i<N; i++){
id[i] = i;
sz[i] = 1;
actualList[i] = i;
}
}
// returns the root of the component the integer is in
private int root(int i){
while(id[i]!=i){
i = id[i];
}
return i;
}
// weighted quick union
public void union(Integer p, Integer q) {
int pRoot = root(p);
int qRoot = root(q);
if (sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] = sz[qRoot] + sz[pRoot];
} else {
id[qRoot] = pRoot;
sz[pRoot] = sz[pRoot] + sz[qRoot];
actualList[pRoot] = qRoot; // this is the crucial step
}
}
public void remove(int x){
union(x, x+1);
}
public int successor(int x){
return actualList[(root(x+1))];
}
}