带路径压缩算法的加权 Quick-Union

有一种“带路径压缩的加权快速联合”算法。

代码：

public class WeightedQU 
{
    private int[] id;
    private int[] iz;

    public WeightedQU(int N)
    {
        id = new int[N];
        iz = new int[N];
        for(int i = 0; i < id.length; i++)
        {
            iz[i] = i;
            id[i] = i;
        }
    }

    public int root(int i)
    {
        while(i != id[i])
        {
            id[i] = id[id[i]];   // this line represents "path compression"
            i = id[i];
        }
        return i;
    }

    public boolean connected(int p, int q)
    {
        return root(p) == root(q);
    }

    public void union(int p, int q)   // here iz[] is used to "weighting"
    {
        int i = root(p);
        int j = root(q);
        if(iz[i] < iz[j])
        {
            id[i] = j;
            iz[j] += iz[i];
        }
        else
        {
            id[j] = i;
            iz[i] += iz[j];
        }
    }
}

问题：

1. 路径压缩如何工作？id[i] = id[id[i]]意味着我们只到达节点的第二个祖先，而不是根。

2. iz[]包含来自的整数0 to N-1。如何iz[]帮助我们知道集合中元素的数量？

有人可以帮我澄清一下吗？

首先要明白id is a forest. id[i]是的父级i. If id[i] == i代表着i是一个根。

对于一些根i (where id[i] == i) then iz[i]是元素的数量tree植根于i.

public int root(int i)
{
    while(i != id[i])
    {
        id[i] = id[id[i]];   // this line represents "path compression"
        i = id[i];
    }
    return i;
}

路径压缩如何工作？id[i] = id[id[i]]意味着我们只到达节点的第二个祖先，而不是根。

当我们沿着树向上查找根时，我们将节点从它们的父母移动到它们的祖父母。这会部分压平树。请注意，此操作不会更改节点所属的树，这就是我们感兴趣的全部。这就是路径压缩技术。

（你确实注意到了循环，对吧？while(i == id[i])终止一次i是根节点）

iz[]包含来自的整数0 to N-1。如何iz[]帮助我们知道集合中元素的数量？

代码中存在转录错误：

for(int i = 0; i < id.length; i++)
{
    iz[i] = i; // WRONG
    id[i] = i;
}

这是正确的版本：

for(int i = 0; i < id.length; i++)
{
    iz[i] = 1; // RIGHT
    id[i] = i;
}

iz[i]是根位于的树的元素数量i (or if i则不是根iz[i]未定义）。所以应该初始化为1, not i。最初，每个元素都是一个单独的“单例”大小的树1.