java如何实现加权快速联合算法？

Question

我目前参加了普林斯顿算法课程（第1部分），它讨论了对快速联合算法的改进，通过维护一个额外的数组sz[I]来计算树根I中的对象数，但它没有说明如何做到这一点

该计数器应在何处以及如何实施？我试过用root方法，但我意识到它不能计算给定对象的子对象

这是课程中给出的不变代码：

public class QuickUnionUF {
    private int[] id;
    public QuickUnionUF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }
    private int root(int i) {
        while (i != id[i]) i = id[i];
        return i;
    }
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

Answer 1

要执行加权并集，需要知道每棵树的权重，所以制作并行数组wt[]，其中wt[k]包含根为k的树的大小。初始重量为1

将较小的树粘贴到较大树的根上，并更新权重

public void union(int p, int q) {
    int i = root(p);
    int j = root(q);
    if wt[i] < wt[j] { 
        id[i] = j;
        wt[j] += wt[i] 
    }
    else {similar for j->i}
}

初始化

public class QuickUnionUF {
  private int[] id;
  private int[] wt;
  public QuickUnionUF(int N) {
    id = new int[N];
    wt = new int[N];
    for (int i = 0; i < N; i++) {
       id[i] = i;
       wt[i] = 1;
    }
  }