并查集

package 板子;import java.util.Arrays;public class UnionFind {    int [] parent;//每个节点对应的父节点    int []size; //对应集合里面有多少个节点    int branchCount;//多少个集合    public  UnionFind(int n){        this.branchCount=n;        this.parent=new int[n];        this.size=new int[n];        Arrays.fill(size,1);//刚开始每个集合初始化都为1        for(int i=0;i<n;i++){            parent[i]=i; //每个集合的父节点都是自己        }    }    public int find(int x){        return parent[x]==x?x:(parent[x]=find(parent[x]));    }    public  boolean unite(int x,int y){        x=find(x);        y=find(y);        if (x==y){            return false;        }        //按照对应的大小合并        if (size[x]<size[y]){            int temp=x;            x=y;            y=temp;        }         parent[y]=x;        size[x]+=size[y];        --branchCount;        return true;    }    public boolean connected(int x, int y) {        return find(x) == find(y);    }    public int branchCount() {        return branchCount;    }}