并查集代碼實作

該作者已經将并查集原理講述的非常清楚 傳送門：部落格位址

并查集實作代碼

使用了路徑壓索和連接配接優化

package com.algorithm.unionFind;

public class UnionFind {
    private int [] group, groupSize;
    private int groupNum;

    /**
     * 初始化
     * @param num
     */
    UnionFind(int num){
        group = new int[num];
        groupSize = new int[num];
        groupNum = num;
        for(int i = 0;i<num;i++){
            group[i] = i;
            groupSize[i] = 1;
        }
    }

    /**
     *
     * 查詢節點node屬于的組
     * @param node
     * @return
     */
    public int find(int node){
        while(node != group[node]){
            group[node] = group[group[node]];
            node = group[node];
        }
        return node;
    }

    /**
     * 連接配接兩個節點nodePre,nodePost，使之屬于同一個組
     * @param nodePre
     * @param nodePost
     * @return
     */
    public void union(int nodePre, int nodePost){
        int nodePreRoot = find(nodePre);
        int nodePostRoot = find(nodePost);
        if(nodePostRoot == nodePreRoot) return ;
        if(groupSize[nodePostRoot] > groupSize[nodePreRoot]) {
            group[nodePreRoot] = nodePostRoot;
            groupSize[nodePostRoot] += groupSize[nodePreRoot];
        }
        else{
            group[nodePostRoot ] = nodePreRoot;
            groupSize[nodePreRoot] += groupSize[nodePostRoot];
        }
        groupNum -- ;
    }

    /**
     * 判斷兩個節點之間是否是聯通的
     * @param nodePre
     * @param nodePost
     * @return
     */
    public boolean isConnected(int nodePre, int nodePost){
        return find(nodePre) == find(nodePost);
    }

    /**
     * 擷取組的數目
     * @return
     */
    public int getCount(){
        return groupNum;
    }

}