UnionFind(并查集)

UnionFind

public class UnionFind {
    private int []parent;
    //初始化每个节点
    public UnionFind(int n){
        if(n<=0){
            throw new IllegalArgumentException("n must > 0");
        }
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=-1;
        }
    }
    //判断输入的下标是否有效
    public void validate(int v1){
        if(v1<0&&v1>=parent.length){
            throw new RuntimeException(v1+" is not a valid index.");
        }
    }
    //返回该节点所在的整棵树的大小
    public int sizeof(int v1){
        return -parent[find(v1)];
    }
    //返回该节点的父节点
    //如果该节点是根结点，返回树的大小
    public int parent(int v1){
        return parent[v1];
    }
    //判断两个节点是否连接
    public boolean is_connected(int v1,int v2){
        return find(v1)==find(v2);
    }
    //连接两个节点
    public void connect(int v1,int v2){
        if(is_connected(v1,v2)){
            return;
        }
        int size1=-parent[find(v1)];
        int size2=-parent[find(v2)];

        if(size1>=size2){
            parent[find(v2)]=find(v1);
            parent[find(v1)]=-(size1+size2);
        }
        else {
            parent[find(v1)]=find(v2);
            parent[find(v2)]=-(size1+size2);
        }
    }
    //找该节点的根节点
    public int find(int v){
        int root=v;
        while(parent[root]>=0){
            root=parent[root];
        }
        //路径压缩，更新根节点
        while(parent[v]>=0){
            parent[v]=root;
            v=parent[v];
            if(v<0) break;
        }
        return root;
    }

    public static void main(String[] args) {
        UnionFind kun=new UnionFind(10);
        kun.connect(1,0);
        kun.connect(0,3);
        kun.connect(2,4);
        kun.connect(2,5);
        kun.connect(6,7);
        kun.connect(8,9);
        kun.connect(6,8);
        kun.connect(2,6);
        System.out.println(kun.sizeof(6));
        System.out.println(kun.sizeof(0));
        System.out.println(kun.sizeof(2));
    }
}