algorithm - 我们可以为 Quick Union 算法的根部分设置一个 if 循环吗？

Question

在下面的Quick Union algorithm imlementation中，在root方法中我们可以有一个if循环(例如if(i != id [i])而不是while循环吗？我认为它同样有效。那么为什么他们使用了 while 循环吗？

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

组件可以用比一级更高的树来表示。要获取组件 ID，您需要一直向下查找到根目录。例如尝试

s = new QuickUnionUF(3);
s.union(0,1);
s.union(1,2);
System.out.println(s.connected(0,1));  // <== prints false when using 'if'