并查集

并查集结构

　　解决部分节点存在先后顺序的问题。

初始化

把每个点所在集合初始化为其自身。

通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

查找

查找元素所在的集合，即根节点。

合并

将两个元素所在的集合合并为一个集合。

1、非环结构

class UnionFind{
　　
　　int [] parent;

    public UnionFind(int [] parent){
        this.parent = parent;
        for(int i=0;i<parent.length;i++){
            parent[i] = i;
        }
    }

    public void union(int i,int j){
        parent[find(i)] = find(j);
    }

    public int find(int i){
        if(i!=parent[i]){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }
}

2、添加秩处理出现环的情况

  private class UnionFind {

        private int[] parent;
        /**
         * 以 i 为根结点的子树的高度（引入了路径压缩以后该定义并不准确）
         */
        private int[] rank;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            if (rank[rootX] == rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度仅加了 1
                rank[rootY]++;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度不变
            } else {
                // 同理，此时以 rootX 为根结点的树的高度不变
                parent[rootY] = rootX;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }