并查集是一种数据结构，用于解决集合的连通性问题。
    并查集主要包括以下几种基本操作：

    • 初始化： 建立一个新的并查集，其中包含s个单元素集合
    • 查询： 把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并
    • 合并： 找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了

    并查集一般用树形结构，同一个集合的元素具有相同的根结点。
    比如：find(D)和find(F)分别返回元素D和元素F所属集合的代表A和H：
    image.png
    union(D, F)将元素D和元素F所在的集合合并：
    image.png
    合并的依据：结点多的集合的根结点作为新集合的根结点，这样可以有效控制树高。(按秩优化)
    路径压缩： 对于一个树来说，它的根节点下面可以依附着许多的节点，因此，可以尝试在find的过程中，从底向上，如果此时访问的节点不是根节点的话，那么可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩

    image.png

    代码实现：

    1. class UnionSet {
    2.         int[] fa;
    3.         int[] size;
    5.         //初始化
    6.         UnionSet(int n) {
    7.             fa = new int[n + 1];
    8.             size = new int[n + 1];
    9.             for(int i = 0;i <= n;i++) {
    10.                 fa[i] = i;
    11.                 size[i] = 1;
    12.             }
    13.         }
    15.         int find(int x) {
    16.             if(fa[x] == x) return x;
    17.             int root = find(fa[x]);
    18.             fa[x] = root;//路径压缩
    19.             return root;
    20.         }
    22.         void merge(int a,int b) {
    23.             int ra = find(a);
    24.             int rb = find(b);
    25.             if(ra == rb) return;
    26.             //按秩优化
    27.             if(size[ra] < size[rb]) {
    28.                 fa[rb] = ra;
    29.                 size[ra] += size[rb];
    30.             } else {
    31.                 fa[ra] = rb;
    32.                 size[rb] += size[ra];
    33.             }
    34.         }
    35.     }