并查集 (union & find) 是?种树型的数据结构，?于处理理?些不交集(Disjoint Sets)的合并及查询问题。

一般有2个操作：

1. Find： 确定元素属于哪?个?集。它可以被?来确定两个元素是否属于同?子集。
2. Union:将两个子集合并成同?个集合。

算法核心思想

（1）最开始时候，每个元素构成一个集合，起parent就为元素本身

（2）1和3元素合并

（3）2和3合并

（4）4、5、6元素合并

（5）1、2、3 和 4、5、6元素合并

代码

1. 最简单的并查集代码

class UnionFind {
    int[] parent;
  
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

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

改进一下：在实际的合并过程，往往会出现如下图情况，形成以及链式集合，这样查询的时候效率很低，parent数组存放了太多的无用信息，其实我们只需要关注的就是根节点信息就可以了。

我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。

class UnionFind {
    int[] parent;
    int[] rank;
  
    public UnionFind(int n) {
      parent = new int[n];
      for (int i = 0; i < n; i++) {
          parent[i] = i;
      }
      rank = new int[n];
      Arrays.fill(rank, 1);
  	}
  
    public void union(int x, int y) {
      int i = find(x);
      int j = find(y);
      if (i == j) {
          return;
      }
      if (rank[i] > rank[j]) {
          parent[j] = i;
      } else {
          parent[i] = j;
      }
      if (rank[i] == rank[j]) {
          rank[i]++;
      }
  	}
}