并查集

并查集

• 解决连接问题
  • 网络中节点的连接状态
• 数学中的集合类实现

并查集的实现

• 基本实现

// Quick Find
public class UnioFind1{
    
    private int[] id;

    public UnioFind1(int size){
        id = new int[size];

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

    public int getSize(){
        return id.length;
    }

    // 查找元素p所对应的集合编号
    private int find(int p){
        if(p<0||p>=id.length){
            throw new IllegalArgumentException("p is out of bound");
        }
        return id[p];
    }

    // O(1)
    // 查看元素p和元素q是否所属一个集合
    public boolean isConnected(int p,int q){
        return find(p) == find(q);
    }

    // O(n)
    // 合并元素p和元素q所属的集合
    public void unionElements(int p,int q){
        int pId = find(p);
        int qId = find(q);
        if(pId==qId){
            return;
        }

        for(int i=0;i<id.length;i++){
            if(id[i]==pId){
                id[i]=qId;
            }
        }
    }
}

// Quick Union
public class UnioFind2{
    
    private int[] parent;

    public UnioFind2(int size){
        
        parent = new int[size];

        for(int i=0;i<size;i++){
            parent[i]=i;
        }
    }

    public int getSize(){
        return parent.length;
    }

    // 查找过程,查找元素p所对应的集合编号
    // O(h)复杂度,h为树的高度
    public int find(int p){
        if(p<0||p>=id.length){
            throw new IllegalArgumentException("p is out of bound");
        }
        while(p!=parent[p]){
            p = parent[p];
        }
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度,h为树的高度
    public boolean isConnected(int p,int q){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度,h为树的高度
    public void unionElements(int p,int q){
        
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot==qRoot){
            return;
        }

        parent[pRoot] = qRoot;
    }
}

• Quick Union 基于size的优化

// Quick Union 基于size的优化
public class UnioFind3{
    
    private int[] parent;

    // sz[i]表示以i为根的集合中元素个数
    private int[] sz;

    public UnioFind3(int size){
        
        parent = new int[size];
        sz = new int[size];

        for(int i=0;i<size;i++){
            parent[i]=i;
            sz[i]=1;
        }
    }

    public int getSize(){
        return parent.length;
    }

    // 查找过程,查找元素p所对应的集合编号
    // O(h)复杂度,h为树的高度
    public int find(int p){
        if(p<0||p>=id.length){
            throw new IllegalArgumentException("p is out of bound");
        }
        while(p!=parent[p]){
            p = parent[p];
        }
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度,h为树的高度
    public boolean isConnected(int p,int q){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度,h为树的高度
    public void unionElements(int p,int q){
        
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot==qRoot){
            return;
        }
        if(sz[pRoot<sz[qRoot]]){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else{
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

• 基于rank的优化

// Quick Union 基于rank的优化
public class UnioFind4{
    
    private int[] parent;

    // rank[i]表示以i为根的集合所表示的树的层树
    private int[] rank;

    public UnioFind4(int size){
        
        parent = new int[size];
        rank = new int[size];

        for(int i=0;i<size;i++){
            parent[i]=i;
            rank[i]=1;
        }
    }

    public int getSize(){
        return parent.length;
    }

    // 查找过程,查找元素p所对应的集合编号
    // O(h)复杂度,h为树的高度
    public int find(int p){
        if(p<0||p>=id.length){
            throw new IllegalArgumentException("p is out of bound");
        }
        while(p!=parent[p]){
            p = parent[p];
        }
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度,h为树的高度
    public boolean isConnected(int p,int q){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度,h为树的高度
    public void unionElements(int p,int q){
        
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot==qRoot){
            return;
        }
        if(rank[pRoot<rank[qRoot]]){
            parent[pRoot] = qRoot;
        }else if(rank[qRoot]<rank[pRoot]){
            parent[qRoot] = pRoot;
        }else{
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

• 路径压缩

private int find(int p){
    if(p<0||p>=id.length){
        throw new IllegalArgumentException("p is out of bound");
    }
    while(p!=parent[p]){
        parent[p] = parent[parent[p]];
        p = parent[p];
    }
    return p;
}

• 路径压缩2

private int find(int p){
    if(p<0||p>=id.length){
        throw new IllegalArgumentException("p is out of bound");
    }
    if(p!=parent[p]){
        parent[p] = find(parent[p]);
    }
    return parent[p];
}