概念

其实并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。

用途

1. 维护无向图的连通性。支持判断两个点是否在同一连通块内。
2. 判断增加一条边是否会产生环：用在求解最小生成树的Kruskal算法里。

操作

并查集主要就三个操作：初始化、合并、查找

初始化

一般来说，并查集的初始化用数组即可，例如数组Tree[i]，i表示某节点，tree[i]表示当前节点的根节点

查找函数

这里的查找和java集合类List中的查找函数get()并不一样，他的作用是查找该节点的根节点，如果集合的parent等于集合的编号（即还没有被合并或者没有同类），那么自然返回自身编号。如果不同那么就可以调用递归函数。 代码如下

    // 并查集查找根节点
    static int findRoot(int x, int[] arr) {
        // 如果集合i的父亲是自己，说明自己就是源头，返回自己的标号
        if (arr[x] == -1)
            return x;
        else // 否则查找集合i的父亲的源头
            return findRoot(arr[x], arr);
    }

若需要在查找过程中添加路径压缩的优化，我们修改上面这个函数为：

    // 并查集查找根节点（优化算法,本质是将路径压缩了）
    static int findRootUseful(int x, int[] arr) {
        int res = 0;
        if (arr[x] == -1)
            return x;
        else {
            res = findRoot(arr[x], arr);
            arr[x] = res; // 将当前结点的双亲结点设置为查找返回的根结点编号
            return res;
        }
    }

合并

上面的图片就是关于合并的解法，至于怎么合并就是要看题目的要求了，详见代码示例中的注释

    //set1表示x所在的集合，set2表示y所在的集合
    // 合并两个集合,至于按照什么原则合并就要按照题目意思了，在这里我定义了两个变量，用以比较set1和set2的某种属性之间的差异
    //如果rankX>rankY,就需要把y的集合合并到x的根节点下，也就是set2[y]=x，否则就是将x的集合放到y的根节点下，即set1[x]=y
    static int rankX = 0;
    static int rankY = 1;
    static void union(int x, int y, int[] set1, int[] set2) {
        x = findRootUseful(x, set1);
        y = findRootUseful(y, set2);
        if (x == y)
            return;
        else if (rankX > rankY) {
            set2[y] = x;
        } else {
            if (rankX == rankY)
                rankY++;
            set1[x] = y;
        }
    }