并查集

并查集結構

　　解決部分節點存在先後順序的問題。

初始化

把每個點所在集合初始化為其自身。

通常來說，這個步驟在每次使用該資料結構時隻需要執行一次，無論何種實作方式，時間複雜度均為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];
        }
    }