动态联通性的三种算法

第一种 对于quick-find的算法实现

public class UF {
    private int[] id;
    private int count;
    public UF(int N) {
        count = N;
        id = new int[N];

        for (int i = 0; i < N; i++) {
            id[i] = i;

        }
    }
        public int count(){
            return count;
        }
        public  boolean connected(int p,int q){
        return  find(p) == find(q);
    }
            //quick-find算法
        public int find(int p){
            return id[p];
        }
        public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        //如果pq之间已经连接，则直接返回
        if (pID == qID) return;
            for (int i = 0; i < id.length; i++) {
                if(id[i] == pID)  id[i] = qID;
            }
            count--;
        }

}

在此算法中，当我们连通（union）连个对象时，先通过find方法找到他们的id[p],id[q]的值，再通过遍历整个id数组，将所有值为pID直接赋值为qID。整个算法的操作速度很快，只需要访问id[]数组一次，但无法处理大型问题，因为每一对输入unio（）都需要扫描整个数组。
quick-union算法

public class UF {
    private int[] id;
    private int count;
    public UF(int N) {
        count = N;
        id = new int[N];

        for (int i = 0; i < N; i++) {
            id[i] = i;

        }
    }
        public int count(){
            return count;
        }
        public  boolean connected(int p,int q){
        return  find(p) == find(q);
    }
            //quick-union算法
        public int find(int p){
            while (p != id[p])  p=id[p];
            return p;
        }
        public void union(int p,int q){
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot)  return;
            id[pRoot] = qRoot;
            count--;
        }

}

quick-union的算法运用了结构树，每个节点都能找到自己的根节点【也许是它自身】，连通对象时，算法通过find先找到p,q的根节点，最后直接将根节点的值赋值【为】q的根节点值，整个算法看似比quick-find快，但在某些输入条件下，并不快于前者，所以我们更推崇第三种。
加权quick-union算法

public class WeightedQuickUnionUF {
    private  int[] id;
    private  int[] sz;
    private int count;
    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
        for (int i = 0; i < N; i++) {
            sz[i] = 1;
        }
    }
        public int count(){
            return count;
        }
        public boolean connected(int p,int q){
        return  find(p)== find(q);
    }
    public int find(int p){
        while (p != id[p]) p=id[p];
        return  p;
    }
    public void union(int p,int q){
        int i =find(p);
        int j =find(q);
        if (i == j) return;
        if (sz[i] < sz[j]) { id[i] = j; sz[j]+=sz[i];}
        else               { id[j] = i; sz[i]+=sz[j];}
        count--;
    }
}

在此算法中，我们依旧利用了树的结构，但多加了一个sz数组表示 各个【根节点】所对应的分量大小，初始值都为1，在连通时，先将根节点找到，之后再比较两根节点的大小，将较小的树的根节点的值赋值【为】较大的树的根节点的值，这样可以保证较小的树总是连接到较大的树上。
第三种算法的增长级为logN