Union-Find算法

动态连通性问题中，如何判断触点是否相连接，可以抽象表述为如何编写程序来过滤掉序列中所有无意义的整数对。
连通性问题只要求我们的程序能够判定给定的整数对p，q是否相连接，但并不要求给出两者之间通路上的所有连接，反而加大了问题的难度。为了简化说明问题，我们不妨自己设计一份API来封装所需要的操作：初始化，连接两个触点，判断包含某两个触点的分量，判断两个触点是否在同一个分量，返回所有分量的数量。
通过自己定义如何连接，我们可以很容易的判断是否连接。

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);
    }
    public int find(int p)
    public int union(int p, int  q)
    public static void main(String[] args){
        int N = StdIn.readInt();
        UF uf = new UF(N);
        while(!StdIn.isEmpty()){
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if(uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
    }
}

上述代码实现了基本的API，还剩下union和find两个函数没有实现。下面来看几种不同的解决方案。

• quick-find

private int find(int p){
    return id[p];
}
public void union(int p, int q){
    int pID = find(p);
    int qID = find(q);
    if(pID == qID)  return;
    for( int i=0; i<id; i++)
        if( id[i] == pID) id[i] = qID;
    count--;
}

quick-find算法中，find()操作只需要访问数组一次，但是每一次归并两个分量的union()操作需要访问数组(N+3)_{(2N+1)次。假使我们使用quick-find算法解决连通性问题并最终只剩下一个分量，至少需要调用N-1次的union()，即至少(N+3)(N-1)}N²次数组访问。

• quick-union

private 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算法将会把触点连接成为一棵树，我们定义一棵树的大小为节点的数量，树中一个节点的深度是它到根节点路径上的链接数，树的高度是它最大的深度。
那么quick-union算法中的find()方法访问数组的次数为1加上给定触点所对应节点深度的两倍。union()方法访问数组的次数为两次find()操作（如果union()中两个触点位于不同的分量中还要再加1）。

• weighted-quick-union
  我们很容易发现quick-union算法在最坏的情况下，仍然是平方级别的，此时形成的树没有分岔。我们可以简单的修改从而避免这一情况。quick-union中随意将一棵树连接至另一棵树，现在我们记录每一颗树的大小以确保将小树连接在大树上。

public class weightedQuickUnionUF{
    private int[] id;
    private int[] sz;
    private int count;
    public WeightedQuickUnionUF(int N){
        count = N;
        id = new int[N];
        for(int i=0; i<N; i++)  id[i] = i;
        sz = new int[N];
        for(int i=0; i<N; i++)   id[i] = 1;
    }
    public int count(){
        return count;
    }
    public boolean connected(int p, int q){
        return find(p) == find(q);
    }
    private 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--;
    }
}