什么是并查集 ？

并查集是一种树形的数据结构

并查集可以高效的进行两种操作

• 查询元素p 和 q 是否属于同一组
• 合并元素p 和 q 所在的组

下面手动实现一个并查集案例

/**
 * 并查集的实现案例
 */
public class UF_Tree {
    /**
     * 记录并查集 中的分组数量
     */
    private int count;

    /**
     * 采用一个数组 数组下标表示元素
     * 数组的值表示 所在的树 （用根节点表示）
     */
    private int[] eleAndGroup;

    /**
     * 记录每个元素作为根节点 代表的树的元素个数
     * 这样在并查集的合并的过程中 让元素少的树 合并到 元素多的树  可以尽可能的减少树的深度
     */
    private int[] sz;

    /**
     * 初始化并查集
     * 表示初始化 N 个分组的 并查集
     *
     * @param N
     */
    public UF_Tree (int N) {
        //初始化并查集的分组大小
        count = N;

        eleAndGroup = new int[N];
        sz = new int[N];

        for (int i = 0; i < N; i++) {
            eleAndGroup[i] = i++;
            sz[i] = 1;
        }

    }

    /**
     * 返回并查集中有多少组
     *
     * @return
     */
    public int getCount () {
        return count;
    }

    /**
     * 寻找元素p 所在并查集里的分组 （找树的根结点）
     *
     * @param p
     * @return
     */
    public int find (int p) {
        while (true) {
            if (p != eleAndGroup[p])
                p = eleAndGroup[p];
            else
                return eleAndGroup[p];
        }
    }

    /**
     * 判断元素p 和 元素q 是否存在于同一颗树中
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isConnected (int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 合并p , q 元素所在的分组
     *
     * @param p
     * @param q
     */
    public void union (int p, int q) {
        //查看p,q元素所在分组树 的 根结点
        int pRoot = find(p);
        int qRoot = find(q);
        //存在同一颗树 ，直接返回
        if (pRoot == qRoot)
            return;

        //先判断各自树的深度 （这里用元素的个数 来类比深度）
        //让元素少的树 合并到 元素多的树
        if (sz[pRoot] > sz[qRoot]) {
            eleAndGroup[qRoot] = eleAndGroup[pRoot];
            sz[pRoot] += sz[qRoot];
        }else {
            eleAndGroup[pRoot] = eleAndGroup[qRoot];
            sz[qRoot] += sz[pRoot];
        }
        --count;
    }

}